I have to agree with TypeX45, sounds like a driver issue. Are you using the drivers that came with the printer, and if so, have you tried downloading the most current drivers from HP's website?
My 712C runs off the XP drivers just fine without installing any of HP's software. You might try that as well.