Eu acho que você não adicionou o PPA que tem as ferramentas que você está procurando. De instruções do wiki do Ubuntu
Configure o PPA das Ferramentas de visualização do Google Play para desenvolvedores
O PPA possui as ferramentas e dependências para suportar Preciso, Quantico e Raring. Adicione o Ubuntu Touch PPA adicionando a seguinte entrada de lista de fontes personalizadas ao seu arquivo /etc/apt/sources.list.
No seu computador, pressione Ctrl + Alt + T para iniciar um terminal.
sudo add-apt-repositório ppa: phablet-team / tools
ou se o add-apt-repository não estiver disponível, acrescente o seguinte ao seu sources.list:
deb link [dist-codename] main
deb-src link [dist-codename] main
* Nota: substitua [dist-codename] por precis, quantal, raring ou saucy.
Faça o seguinte:
sudo apt-get update
sudo apt-get instalar phablet-tools android-ferramentas-adb android-tools-fastboot
Espero que isso seja útil.