Tires should scrub-in in less than 500 miles. Probably as little as 200. The owners manual says about 200 miles IIRC.
Could be as simples as tire pressures. Maybe they even mounted them on the wrong side of the car.
How cold is it where you are now. Our tires don't have much grip below 40-45 degrees either.