Desde o Ubuntu 12.04 existe uma nova ferramenta para alterar os aplicativos padrão. De acordo com essa resposta , precisamos usar gsettings agora. Posso confirmar que funciona no Ubuntu 13.10.
Por exemplo, se você quiser usar o Sakura como terminal padrão:
gsettings set org.gnome.desktop.default-applications.terminal exec 'sakura'