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:
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:
The hplip-3.11.1 auto discovered the correct PPD:
I haven’t tested this with 4×6″ photos and the like yet but an A4 test page worked fine.