Most people do remove the passenger side fender to firewall brace to add a second battery. Then again, most people do NOT remove their driver's side fender to firewall brace. Not sure why you removed yours? Can you add it back?
Most people get the second battery tray for the diesel versions of the 2001-2007 Classic GMT800 truck. They remove the lower brace and replace it with the tray, and then remove the upper brace altogether.
I added a second battery to my 2005 quite a few years ago, and when I did, I researched the topic extensively, across many GM truck related forums.
Of all the people who described and photographed their second battery install for this model year series, I am aware of only two people who did not remove that passenger side upper fender brace.
The first person used a much smaller battery, that happened to fit underneath the fender brace. The second person (me) used a full size battery identical to the original battery, but modified the passenger brace so that it would clear the battery and clear the hood when closed. I didn't want to lose the benefit of that fender brace in a collision.
But most people, including GM, simply remove that upper brace to install a second battery. (This does not apply to NNBS, only NBS).