Did you install the software and wait until it told you to plug in the printer?
Printers are the most annoying things when they don't work!
Sometimes, there are problems with stacked printer installs and leftovers in the registry from previous printers. You'd think that HP had the concept of printer software under control by now, but they still have a way to go.
Make sure that you check the HP support site
and if you can't find anything useful, you can always use their free email support. I've gone that route a number of times and it can be frustrating because they keep trading techs and they'll tell you to do the things you've already done, but they do keep at it and eventually might come up with a solution, such as a patch.
Another idea is to check the HP site for a software/driver download - sometimes the ones online are newer than what came with the printer and will work better.