Is there a possibility that the paper manufacturing has changed? Hp has had HP Matte Litho-realistic paper for ages, and just last year they changed it - apparently a different manufacturer. Everything went out the window for me. Couldn't get my profiles to work and the paper has buckling issues. Never the same as the old paper because it just wasn't the old paper.
Obviously it can't be outdated inks or you would have mentioned that. Can't be outdated printheads because you would have put brand new ones in when you rebuilt the machines.
Color is on, and accurate. Have you tried a different print setting?
Use more passes and not maximum detail? Or vice versa, max detail without more passes?
It can make a huge difference. I had a terrible issue with inks once and changed my settings and voila, it worked.
Re: the Paper Advance Calibration - you know, over the years, we develop tricks that we hear or try and if it works, it just works. The Paper Advance Calibration after running through the diagnostics seems to work like magic when changing papers.
I know HP discusses it in relation to banding, but I believe it does a whole lot more. Just as unplugging and replugging the printer works some crazy magic and HP themselves often recommend it, PAC is something that gets the printer "reset" and back to the basics, running right.
Just my experience - I would try it and see if doing that and choosing a maximum detail without more passes does make any difference. Yours seems like it should be easy enough to troubleshoot, but it's just not that easy apparently.
I just advocate trying different approaches until stumbling, methodically upon the right fix or right combination of fixes. That's why I document my progress and make notes, so as not to duplicate efforts.
Always, I find that going back to initial remedial steps sometimes clears even difficult problems unless there are mechanical failures or electrical issues.
If you try my suggestions, some one thing might change, and could make a difference. If not, then back to the drawing board.
I think I explained the sequence which has often worked for me. My experience about the printer resetting itself by using this sequence is grounded in HP's literature and my own personal experience.
I offer it in the spirit of really trying to help you solve this issue without reverting to an outside fix such as using a hair dryer.
I believe there is a fix, maybe we just haven't hit upon it yet.
Good luck, anyway,
Mark