Don't know for sure but I thought I would mention it. Possibly a problem with the printer's jetdirect network card (if it is a network printer which I'm pretty sure it is unless you're using it as a standalone personal printer), find out what version jetdirect card is installed in that printer (600 series maybe), go to hp's site, download the required hp printer mgmt software and firmware update, upload the firmware, power cycle the printer and attempt to print some test pages.
Thinking about it, it possibly may have something to do with the printer maintenance kit you had them install recently. Maybe it wasn't installed properly or maybe the kit was defective. Could be a few things, printer problems usually can't be diagnosed successfully over the phone.
Open up the printer's config page by typing it's ip address in a browser (assuming again it's a network printer), maybe there are some errors listed there that you can glean some constructive info on.
Check the network cable that the printer is attached too, replace it with another just to see how it improves. Attach the printer to a different location in the network, change the hub or switch it's connected to.
Again, like I said, there's lot's to check out.
Let us know how this works out for you.