Check the alignment settings. There's a good thread on here somewhere. The 'search' tool should find it. Sadly many 'alignment' centres wouldn't know a good alignment if it hit 'em in the face. Worth a second opnion. Considering the first lot couldn't get the wheel weights spot on, I'd doubt their skills.
Although the tyres are new, check thoroughly for bulges or sidewall blisters. I've seen new tyres with hideous defects (albeit rarely).