After digging up a little bit, I found a lots of these message in my dmesg output:
[1305902.871825] type=1400 audit(1310620543.587:75): apparmor="STATUS" operation="profile_remove" name="/usr/bin/evince" pid=20166 comm="apparmor
It was obvious that apparmor [1] was blocking Evince to run outside Gnome session over SSH. A solution to disable the AppArmor block on Evince over SSH connection was suggested here [2]:
#inside the gnome-terminal
sudo ln -s /etc/apparmor.d/usr.bin.evince /etc/apparmor.d/disable
sudo /etc/init.d/apparmor restart
And voila! Now Evince can again be launched over SSH.
[1] http://en.wikipedia.org/wiki/AppArmour
[2] http://ubuntuforums.org/showthread.php?t=1472642