I had a similar problem with pdf files in Nautilus 3.2.1 (Debian testing). After installing Adobe Reader 9 from debian-multimedia.org I had the option to open pdf documents with Adobe Reader using the "Open with" menu after right clicking on the file, but choosing properties and tab "Open with" Adobe Reader would not show up.
There were no flaws that I could find in ~/.local/share/applications/AdobeReader.desktop, ~/.local/share/applications/mimeapps.list, /usr/share/applications/AdobeReader.desktop, /usr/share/applications/evince.desktop or /usr/share/applications/mimeinfo.cache (though I did add '%U' to the Exec line of AdobeReader.desktop as suggested here: http://fossplanet.com/f12/nautilus-3-2-1-file-associations-207347/
I found that a simple change in /usr/share/gnome/applications/defaults.list
made the change I was looking for. Searching for 'pdf' in the editor showed me the line 'application/pdf=evince.desktop' that I changed to 'application/pdf=AdobeReader.desktop
'. I saved the file and right away it worked the way I wanted it to (no need to log out or restart).
It may not be the canonical way of solving it, but it worked for me.