o programa instalado tem um .desktop
que precisa ser editado para ser listado na lista "open with list" do nautilus
para fazer isso, você primeiro tem que localizar esse arquivo
ls /usr/share/applications/'
você deve conseguir adivinhar o .desktop
associado ao seu programa.
digamos que eu queira adicionar vlc à lista, edito o arquivo da área de trabalho com
sudo gedit /usr/share/applications/vlc.desktop
e altere Exec=vlc
para Exec=vlc %u
no seu caso, você edita:
sudo gedit /usr/share/applications/AdobeReader.desktop
e altere Exec=AdobeReader
para Exec=AdobeReader %u