Thanks for the suggestions Willy,
bkencairn, did you find a solution or are you still experiencing the problem?
Does "Print as images" help with outputting the content to paper (as a workaround until we figure out what is causing the initial problem)?
As Willy asked - does this happen with some files or with all? If it's only some - can we have a copy of one such to test at our end please?