Eu tive o mesmo problema e resolvi com:
$ sudo apt-get install apparmor-utils
$ sudo aa-complain /usr/bin/evince
Isso muda o perfil do apparmor para evince em complain mode . Isso significa que o apparmor irá reclamar no syslog sobre cada ação do evince que deve ser negada (de acordo com o perfil) ... mas permite isso mesmo assim.
Claro que esta não é a melhor solução, pois todo o perfil é "desativado". Mas como eu não sei como convencer o apparmor a permitir que evince faça mkdir em alvos com link simbólico fora de ~ (que é a razão da negação), isso funciona bem para mim.