I un-installed all the hplip packages on the box from the Software Manager to start with.

Then I followed the instructions here http://hplipopensource.com/hplip-web/install/manual/distros/linuxmint.html

You definately need the latest hplip tarball. (I used hplip-3.11.1.tar.gz)

Once the software was installed per instructions I ran:

sudo hp-setup

My printer is plugged into the wired Ethernet network.

I chose manual discovery because generally I switch auto discovery protocols off and firewalls tend to stop them working too. Enter your printer IP:

Screenshot-HP Device Manager - Setup

HPLIP Auto Discovered Printer

The hplip-3.11.1 auto discovered the correct PPD:

HPLIP Discovers correct PPD

Done.

I haven't tested this with 4x6" photos and the like yet but an A4 test page worked fine.