When I originally setup my Mac Mini a few years ago (with Leopard), I had some issues getting the printer setup on my network using CUPS. Having upgraded to Lion a couple of weeks ago, the printing problems returned.
The first problem I had was that my printer, an HP Deskjet 5150, was not on the supported list of Apple printer drivers. HP were similarly useless in not providing a driver.
The answer was found in the open source community. A quick download and install of Ghostscript, Foomatic-RIP and HPIJS make the correct driver available (along with many other printer drivers).
This allowed me to add my printer, but upon trying to print, the print queue window would report that it was "Unable to get printer status". Not helpful.
The remote printer is connected to my Netgear ReadyNAS Duo which runs an embedded Linux distribution and uses CUPS as the print server. Despite trying to dig into the debug options, I was not able to fix the printing error.
The default method of setting up a printer on a Mac is to use Bonjour for auto discovery. This uses the Internet Printing Protocol (IPP) under the hood but was failing. Attempts to setup the IPP queue manually also failed.
The fix that worked for me was to set up the printer as an SMB (Windows) printer. This uses the ReadyNAS's Samba install and printing now works! Not ideal, but does the job.