It sounds like a driver issue. The HP UPD very often works as a replacement driver in more cases then it doesn't. Sometimes this is already part of the drivers included with Windows, but this isn't always the case. I would suggest downloading it and having it handy, just in case it isn't part of your Windows installation.
If you need to see how to install the driver, here's a guide on how to do it. You will need to install the printer manually, since it sounds like Windows thinks the best driver is the one that doesn't work. The link to the driver is in the guide.
Your printer is new enough to ship with the PCL6 personality, so chances are good the printer will accept the PCL6 driver. If you have problems using PCL6 with this printer, use the PCL5 driver.