Esta opção foi removida, evidentemente 12.04 foi a última versão a ter essa opção. Há um bug ainda aberto aqui:
Recentemente atualizei de 12.04 para 14.04 e não vejo open with no menu de contexto do nautilus nas pastas. Ela costumava estar em 12.04 e eu a usei para tocar música em pastas usando o VLC. Como faço para recuperá-lo em 14.04?