I found a lot of discussion about it but never really found a clear answer. It ended up being quite simple in the end. I guess I'll just post it here so it might be useful for someone who had the same problem as me. The problem being Mint 16 saying the print is completed but the printer actually did nothing. Looks like the included hplip is faulty and/or incompatible with this printer.
Download the latest HPLIP drivers from here.
Current version is 3.14.4
Once downloaded, open a terminal inside your download folder. (Right-Click + Open in terminal)
Then type this command. sh hplip-3.14.4.run (Change version number to current version)
Make sure you overwrite and/or update every file as asked. When they ask you what to do with the old hplip installed, type i. (Remove and Re-install)
This fixed it for me. I hope this will help someone.