Posso confirmar o problema no Ubuntu 12.04 com o Evince 3.4.0 instalado. Dado como isso ocorre tanto no Evince quanto no Okular, é provável que haja um problema com o backend PDF, libpoppler. Você pode querer reportar um bug e fazer um link para o arquivo de amostra. Essa é a única maneira infalível de consertar isso.
Como solução alternativa, aconselho usar o visualizador de PDF embutido (e proprietário) do Chrome. Além disso, você deve instalar o Adobe Reader no Ubuntu Software Center. Ele deve cuidar de todos os problemas de dependência automaticamente.