I deleted the printer from printer settings, and clicked the "Show in finder" folder, then deleted the "hp" folder under /Library/Printers/
Then I re-added it in the system preferences (NOT downloading any drivers from HP's site). It gave me a pop up that said "Drivers need to be downloaded from Apple", and then it downloaded and installed them successfully - it now prints fine and the issue is resolved.
Biting the hand that feeds IT
