Some mechs naturally have quite a lot of play but still shift OK. It would have to be really bad to affect shifting.
First of all, I would experiment more with cable tension even if you do think the indexing is spot on already. It might be possible to improve shifting to smaller cogs without compromising shifting the other way too much. I reckon cable tension is most likely to be the problem because the cable has just been replaced.
If the chain doesn't have any stiff links (check), the chain and cassette is most likely to be fine, and the mech won't have suddenly deteriorated. If the mech was faulty, it would have been shifting poorly with the previous chain and cassette too.