I've seen Vista not be able to connect to a printer using the "Add a printer" method, but be able to find it just fine if you let the latest version of the HP printer's drivers and complete software package do all the finding and connecting during normal software and driver installation. It's weird... er... well... not really, now that I think about it... I've seen that with Canon and Lexmark printers a time or two, too.
There's also a possibility (and this is basic, and you've probably already checked it, but) if it's a normal network IP-based connection on the computer; and if the LAN's DHCP handler has reassigned the printer a new IP address since whenever the printer was added, then it's entirely possible that the computer is trying to "talk" to the printer at one IP address when, in fact, the printer has since moved to a different one. I know it's really basic, but I've been embarassed more than once overlooking checking that simple little thing.
If it's not what's in the second paragraph, above, then maybe what's in the first paragraph will do it. De-install the printer, and all of its software and drivers from the machine. Search through the registry and really and truly make sure that all entries related to that printer are gone. Make sure that all folders which contained the drivers and/or the printer's software are gone. Really scrub the machine clean of any reference to the printer. Then download the absolutely latest, greatest version of the printer's full software installation package for your OS. Then install it (quite possibly running the installer as administrator) and specify, at the proper point in the process, that the printer is network connected and then let the software go out and find it and then set it up. By so doing, the printer may suddenly be properly seen and communicated with by the computer... seemingly inexplicably, I realize.
I'm not saying that this will necessarily be the solution, but in order to keep from going crazy troubleshooting, this is where I would begin. If it still doesn't work after that, then at least I know I've got a good, clean install of the printer's drivers and software on a machine which had, immediately prior thereto, been scrubbed clean of any knowledge of the printer or its software. That's always the best place to start advanced troubleshooting.
See if doing any of that makes a difference and then report back and we'll figure out what to do next.
