Como OSE apontou, este problema é devido ao AppArmor está restringindo os programas que evidenciam pode iniciar. Você pode adicionar nemo à lista de aplicativos que o Evince tem permissão para executar editando /etc/apparmor.d/usr.bin.evince
(você precisará de privilégios de root)
Encontre a seção desse arquivo que se parece com isso:
# By default, we won't support launching a terminal program in Xterm or
# KDE's konsole. It opens up too many unnecessary files for most users.
# People who need this functionality can uncomment the following:
##include <abstractions/ubuntu-xterm>
##include <abstractions/ubuntu-konsole>
/usr/bin/evince rmPx,
/usr/bin/evince-previewer Px,
/usr/bin/yelp Cx -> sanitized_helper,
/usr/bin/bug-buddy px,
# 'Show Containing Folder' (LP: #1022962)
/usr/bin/nautilus Cx -> sanitized_helper, # Gnome
/usr/bin/pcmanfm Cx -> sanitized_helper, # LXDE
/usr/bin/krusader Cx -> sanitized_helper, # KDE
/usr/bin/thunar Cx -> sanitized_helper, # XFCE
Adicione a linha: /usr/bin/nemo Cx -> sanitized_helper, # Gnome,Linux Mint,etc
Reinicie o AppArmor com
sudo /etc/init.d/apparmor restart
O Evince agora deve ser capaz de lançar o nemo.