Printers are always big trouble makers, in my experience, regardless of the OS... I wish I could give you a direct solution but luckily I haven't had to deal with printers much in years. However, I found several threads with similar problems that suggest an additional step from the ones you've also mentioned:
Read that second reply you'll see it's mentioned that you
The Ubuntu pages also have a printer debugging page that is worth checking out. If nothing else, I'll leave it here as reference for future search queries:
If you are using the printer over the network you may need to configure firewall rules to let the printer through. If so, I'd recommend using a utility called GUFW (Graphical Uncomplicated FireWall) and check the "reports" tab for activity related to the printer. Select it and click on the "+" icon below to add a new rule for it.
I don't know about HP Laserjets, but when I had to rebuild a Windows machine many years ago for a client to reinstall the printer meant having to connect using USB cable to the computer and then add an IP address for the printer! But I think zenzen has found the solution!