So I bought a new Mac Mini with Lion installed on it, had it install the software from a previous Mac Mini's install (which had CUPS-PDF installed on it), and CUPS-PDF showed up as a printer but didn't work. :(
Then I uninstalled CUPS-PDF, and reinstalled it and it works.
So here's one random Internet Person saying that "Take two aspirin, uninstall and then re-install CUPS-PDF" may just work. :)
It also works for me, uninstall and re-install. I did not need two aspirin, just two minutes. :)