You have some red flags here, which you are aware of. I would wonder why they are changing the locks, was the car repossessed? Was it a thief recovery? If everything worked ok, why the change? Do they have some fear that someone might use the keys they have to get into your car?

As far as it taking a couple of weeks, that could be explained and if course, it can easily be adjusted.