Bem Cristian, caso o teu "celular" só aceite o formato 3gp, encontrei depois de uma pesquisa, o programa Mobile Media Convertor.
Ele converte para uma série de formatos, incluindo o teu desejado "3gp".
Eu não experimentei o programa, como tal, não posso opinar sobre o mesmo.
Ele permite até, "baixar" os vídeos do YouTube e convertê-los para o formato desejado, "3gp" INCLUIDO (como já havia escrito

).
Para instalá-lo, visto que não está presente nos repositórios, deves proceder da seguinte maneira:
Primeiro de tudo, deves instalar as dependências necessárias (se já tiveres estes pacotes instalados, nada será instalado!):
No terminal:
sudo apt-get install libfaac0 mencoder ffmpeg
seguido da tua password e ENTER.
Depois e ainda no terminal:
este comando irá fazer o download do pacote ".deb" do programa para a tua pasta pessoal.
Por último, também no terminal

:
sudo dpkg -i mmc_i386.deb
este comando irá instalar o programa no teu sistema.
Então só terás que o procurar no "dash", utilizando o termo "Mobile Media Converter".
Experimenta e depois "posta" aqui o resultado.
Referência:
http://www.tuxtree.com/2011/12/how-to-install-mobile-media-convertor-in-ubuntu-11-10.html Cumps.