Using a PDF printer in the "print" script step, versus "save as PDF" usually works for me. people with acrobat pro installed should have it already in their printer list, although you can also deploy a free PDF printer such as primoPDF or cutePDF.
I think your issue is possibly a postscript issue, but I'm not sure.
BullZip is another one I use a lot. Thanks to iBev.
Thanks Mike and Joshua for your responses. We offer a vertical market application so requiring clients to install additional software is something of a no go for us. I'm still hopeful though that there will be some kind of solution within FileMaker.
It is surprising that a) this issue still exists; b) there isn't more information about it.