Using gnome-open to open pdf files

Removing exo-utils worked for me perfectly.

Forth Approach

I could reproduce your problem by deleting this file /usr/share/applications/evince.desktop, so make sure you have this file.

Reference.

Third Approach

xdg-open appears to use the configuration of /etc/mailcap. So edit it to associate pdf with evince.

gksu gedit /etc/mailcap  

Look for the lines that begin with application/pdf; application/x-pdf; application/x-bzpdf; application/x-gzpdf. They should look like this to associate pdf with evince:

application/pdf; evince '%s'; test=test -n "$DISPLAY"; nametemplate=%s.pdf
application/x-pdf; evince '%s'; test=test -n "$DISPLAY"; nametemplate=%s.pdf
application/x-bzpdf; evince '%s'; test=test -n "$DISPLAY"; nametemplate=%s.pdf.bz2
application/x-gzpdf; evince '%s'; test=test -n "$DISPLAY"; nametemplate=%s.pdf.gz

Reference.

Second Approach

What is the output of

xdg-mime query filetype foo.pdf  

If the output isn't what we should expect, then:

xdg-mime default evince.desktop application/pdf   

Reference.

First Approach

There are other places that the file associations are set.

You may change the files associations at:

/usr/share/applications/defaults.list 
/usr/share/applications/mimeinfo.cache
~/.local/share/applications/  
~/.gnome/share/apps/ 

Look for "pdf" and for "Nautilus" inside theses files.

I just ran into this problem today, and according to this thread on ubuntuforums.org, it's caused by exo-utils:

http://ubuntuforums.org/showthread.php?t=1729680

exo-tools is a dependency of Thunar (which I installed today), but isn't normally installed in stock Ubuntu, which I guess is why they missed this bug in release.

Removing this packaged (I actually just removed Thunar and all it's deps) fixed the problem for me.