I just signed up to post in this thread, as it seems Zippy and dko did as well. I got this same error message yesterday, when I was simply printing to the Microsoft XPS writer rather than my HP Laserjet printer. Shortly after everything went through, Avast popped up to warn me that this might be a rootkit. Sensing it may be a false positive, I selected the ignore action and found this forum thread. Then today my wife was on her laptop and got the same error at startup time. She also had the printer software installed.
I only got this printer within the last couple of months, and in that time Avast hasn't complained about anything. We just got the executable from the install CD that came with the printer. I ran a boot scan after this happened and the results said "no virus found". However, I checked my virus chest and HPLaserJetService.exe is currently residing in there, with the virus description "Win32:Evo-gen [Susp]". I really am hoping that this is just a false positive, although it makes me wonder what this service was doing that it would set of Avast's alarms.
Included is a screenshot of the error.