Comment 1 for bug 367650

I advise against the solution above. Installing the Samsung binary drivers will install several other libraries outside the purview of apt (e.g., qt libs, libstdc++5). A better solution is to reconfigure the printer.

Go to System => Administration => Printing, select your printer. Where the "Make and Model" of your printer is listed, select "Change..." to select a new print driver. Locate your printer, and click forward. You will be presented with a message titled "Existing Settings", to which you should answer "Use the new PPD (Postscript Printer Description) as is."

Printing a test page should now hopefully succeed (it did for me). Enjoy!