Did they replace the chain too? If not it could be the chain is a little too stretched and not meshing well with the new cassette.

Otherwise I would check derailer hanger alignment and chain length to make sure those are ok.