If you get the following error message while printing in Debian

cups unsupported format 'application postscript'

it could be, that you are missing the package <i>ghostscript-cups</i>. This is a recommended package for cups but normally I do not install recommended packages.

This is the way to make sure recommended packages are installed:

aptitude install --with-recommends PACKAGE

Or make it permanent by adding to you /etc/apt/apt.conf:

APT::Install-Recommends "true";