You may want to delete the printer port as well when you remove the printer in question. Then re-add as necessary. Are you using the Microsoft Add Printer Wizard or are you using the HP JetDirect Admin to install the printer. If you were using the MS Add Printer Wizard try using the HP Jetdirect Admin or vice versa to see if that resolves the issue.
Did you map the printer from the server via the IP address?