Print preview will still be running on the computer, not the printer. If a character ( code point) is rendering on your computer well because the font it's using has that character's glyph in it, it'll look good on preview, but if the font used on the printer itself doesn't have the glyph then....you'll still get boxes/question marks for any characters outside the embedded font's range.
PDFs *can* embed fonts to get around this very problem, but it's not required, and increases the size of the PDFs (not unreasonably, usually, as only the glyphs used get embedded). Sending rendered bitmaps to the printer also gets around this issue. I'm guessing ghostscript does this (font embedding) and evince does not. I don't see any options for this in my version of evince. This also probably isn't a CUPS issue, either as font embedding is more the responsibility of the source application.