Funny, I had all new tires (6 of them at the tune of $250 each) put on my dually just a month ago. I towed almost immediately. Never noticed anything different in towing, squirm, shake, fishtail, sway, passing truck suction and pull, or uneasiness. I replaced with the same identical brand and size and rated tires.
If you used a lesser tire, that might account for some problems. I'd sooner believe the air pressure in the tires is a bigger problem.
Make sure the tires are at the max on the tow vehicle and the trailer. If tires was the only change, then it has to be tires. ... unless you broke a shock on the tow vehicle.