I had this same problem and keinea's solution worked for me. For some reason, it appears that cups-pdf was not installed during my inplace upgrade to Lucid.
Printable View
I had the same problem printing a page with the CUPS PDF virtual printer: "not execute the backend"
I solved the problem running the this command:
#sudo chmod 700 /usr/lib/cups/backend/cups-pdf
I nedded to reinstall, because it wasn't there after the upgrade to 11.10
Then had to run /usr/sbin/cupsenable PDF
Not I could print to PDF again.
( with the system tools menu, icould not fix this )