With a 5 speed transmission the 5th gear is an overdrive gear. When towing you will want the gas engine in the RPM range where it produces its peak torque while in 4th gear at 65 MPH. If your engine produces max torgue is at 4200 RPM as with the current Chevy V-8 and the truck in 4th gear is at 3300 RPM at 65 MPH you have too tall a gearing setup.
Having 3.55 gears you were already in trouble and going to bigger tires was exactly what you should not have done. With GM trucks the 4.10 rear end with the gas engines increases the tow rating by 25% over the identical trucks with the 3.73 rear end. But for your situation check the RPM's at 65 MPH and see how much of a change is needed overall and then see how much you might gain from changing the tires and how much from changing the gears.
Going from 3.50:1 to 4.11:1 will increase engine RPM's by about 14% and going from 3.50:1 to 4.57:1 will increase engine RPM's by about 20%. A shop that specializes in gear swaps should be able to help you check the math.
It may be possible to change only the gears and not the oversized tires presently on the truck which would save you some money.