Printer lights are all on, and yes the Macbook does say that the printer was connected when I have it plugged in directly via USB.
I also tried using our iMac, also plugged into the printer via USB. No luck there either.
I did re-install the driver; reformatting my computer is not an option however.
I think I'm going to give up on it. Something's got to be wrong with the printer itself. If left on, will just suddenly start making noises and it's obvious that something's moving around in there (without me having tried to send a print job, and even when the print queue has been cleared), and this happens randomly. Although... overall, I'm not really surprised... every computer or printer I've ever owned or used that was made by HP would frequently have utterly unexplainable issues!