The update in software update was for 10.8. Now that you've installed the 10.7 stuff is the HP update available again? If not look in HD/Library/Receipts for HP installer receipts and delete them. The HP update should show up again.

You might try deleting the printer, then go to HD/Library/Printers and delete anything HP related, reboot, and let the OS reinstall the software.

You could also try setting it up as an IP printer rather than Bonjour in case it's a Bonjour thing so the computer knows exactly where to go instead of relying on Bonjour.

You can probably get the IP from the config page of the printer. If IP works you might want to lock that address into the printer manually or set up the router to always hand out that address to the printer. It would be under something like Static DHCP or DHCP Reservations in the router config.

Any or all of the above.