Some time ago I had the same problem with the usr/lib/cups/backend/hp failed error message. If I remember it correctly, running chmod 755 /usr/lib/cups/backend as root solved the problem for me since the permissions of /usr/lib/cups/backend were to strict. https://answers.launchpad.net/ubuntu/+source/hplip/+question/93468 gave me this workaround. Maybe bug report #587068 results from the same bug.