The new tires are probably hiding the vibration because they have so much more tread on them. You don't say where the tire wear was, so it's hard to diagnose. I'd guess it's worn out parts in the front end, steering rack bushings. ..... What was the "backs, we're talking fronts" comment about?