Steps were:
- Complete removal of CUPS package including the configuration files
- Reinstall the CUPS package.
- Start the CUPS service with "sudo /etc/init.d/cups restart" in the terminal.
- Reinstall your printers
- Print stuff!
Ubuntu 9.10 Karmic Koala CUPS