Do you have the ghostscript package installed? Might be a stupid suggestion but I did that to myself once and couldn't figure out the problem. If so, run this in a terminal while you try and print a page:
Code:
tail -f /var/log/cups/error_log
and post the results
