Acho que você não instalou o pacote Sublime via PPA. Você pode ter baixado a fonte.
Aqui estão os passos para instalar o pacote Sublime via PPA
sudo add-apt-repository ppa:webupd8team/sublime-text-2
sudo apt-get update
sudo apt-get remove sublime-text*
sudo apt-get install sublime-text
Depois de instalar este Clique com o botão direito em qualquer arquivo php agora você será capaz de ver "Open with Sublime Text 2" ou escolha "Abrir com outro aplicativo" e selecione "Sublime" na lista.
Espero que isso ajude.