Ubuntu – Unable to print from LibreOffice

I recently upgraded to Oneiric and am having a strange printing problem. I can print just fine from Evince, Firefox, and presumably all programs that use the standard Gnome printing backend (as evidenced by the Gnome print dialog). But when I try to print from LibreOffice, the printer spits out the following error message followed by a blank page:

ERROR:
invalidfont
$definefont
STACK:
--nostringval--
/HJTLAV+TimesNewRomanPS-BoldMTFID777HGSet1
--nostringval--
/HJTLAV+TimesNewRomanPS-BoldMTFID777HGSet1
--nostringval--
--nostringval--
13

The printer is a Samsung SCX-7423P using the generic PostScript driver. Everything worked fine under Natty.

Any ideas as to the cause of this problem, and more importantly, how to fix it?

EDIT:

Here's some additional information based on testing I did in response to @scottl's answer below:

• I've tried three Oneiric boxes and only this one exhibits this problem. Unfortunately, it's a shared machine, so the impact is significant.
• Exporting to PDF via either the toolbar button or the print to file option produces a file that Evince prints fine.
• If I print to file and arrange for the filetype to be PostScript instead of PDF, I get the same error when printing on the affected machine using Evince. If I open the file on another machine and print it, everything is OK except that the font doesn't look quite right. I've posted an example PostScript file.
• Even though the error output above mentions the font Times New Roman, the font isn't significant. The PostScript test was done using the font Ubuntu, and the error was the same except for the font name.
• All testing was done using the same printer, as it's the only printer I have access to.