-
Everything is new but the frame. It's an old steel 80's tourer. Maybe the hanger needs looked at again.
Cables are new @Dogtemple
Is play in a freehub normal or not?
-
It's an old steel 80's tourer.
So would have been 126mm OLD originally: seems unlikely, but it's possible the hanger is no longer aligned with a 130mm OLD wheel in there.
Let the shop you paid to do the job in the first place, sort it out. If they can do so without replacing the hub/freehub, then they'll have demonstrated that that amount of play is acceptable.
If everything is brand new and built by someone else, then it really isn't your problem. Sending it out of the shop when it wasn't shifting properly was pretty poor, to put it kindly.
What you've described sounds very much like an alignment problem: a weak spring would only affect shifting in one direction.