It works here with Okular 0.17 on KDE 4.11. As nboth Okular and Evince are affected, I'd suspect poppler, the PDF rendering library used by both.
Do you get any error messages when you run either program from a terminal?
"Insanity: doing the same thing over and over again and expecting different results." (Albert Einstein)