When I started using the z3100 it exhibited symptoms exactly like you describe, but it was a communication problem, not a cleaning issue, even though the head seemed to be shuffling around at one side or the other. I eventually switched some settings in the driver and eliminated the problem.
Is it possible that something changed in your driver (even if you didn't modify a setting)? Have you gone back and tried printing an image on satin paper to see if the problem stays or goes back to your normal printing behavior?
Mike