The brakes and the rear tire have nothing to do with each other.
If you sand down used pads so that you've completely removed any glazed surface, they should bed in just about the same as new pads.
And I would have had Cycle Gear remove the wrong sized tire and order the correct one. You won't get quite as good of cornering traction on a 70-series rear tire as you would on a 60.