What about your print drivers - have you tried updating them?
(that's a suggestion from SJ here at work! She thinks that maybe the problem could be communication between PC and Printer.)

And can you try going to:
Tools > Options > Compatability (tab) > Font Substitutions
Does it tell you that everything is OK?

On the same tab as above - are any of the options ticked in the Options list?

Let me know the results! I'll keep thinking and asking around!