I guess it's not directly a Nautilus bug, but if you right-click on a document
and choose "open with another application", a dialog appears, listing all the
available applications. The problem is that it seems to only list the
applcations that are displayed in the user's menu, discarding the ones that have
been hidden using such a tool as alacarte menu editor.
This is a problem because some applications - like Totem - have been hidden from
the menu for the reason that they're hardly ever launched from the menu, but
rather launch by double-clicking on a video in Nautilus. So, logically, such
applications (most often launched by opening an associated document) should
definitely appear in the "open with another application" dialog.