Apple shows the driver as being available from Software Update. In normal circumstances, when you connect a printer to the Mac it should determine the model of device and then check if the driver is already installed. If the driver is not local then it will check for the driver on Apple's servers and download it if one does exist.
So with the message you are getting the OS believes that there is no driver available, even though this Apple KB article shows that the driver is available.
A quick workaround would be to select the Generic Postscript driver that is included with the OS. This will let you print your starmaps and Klingon wanted posters.
Then if you wanted to try trashing the HP folder in HD > Library > Printers and then adding the printer again, it may kick the OS into getting the correct driver.
Once last thing. How is the printer connected to the Mac? Ethernet, USB or some old Apple proprietary connector? If the later then this could be a contributor to the issue.