Reason for this is application .desktop file missing MimeType specification. For example for me mplayer and thunderbird are not listed as choices for video and mail respectively. To fix this edit application's .desktop file (in /usr/local/share/applications directory, or in ~/.local/share/applications) and run update-desktop-database afterwards (with -v to show its warnings).
