権利関係で3gpなどのコーデックがubuntuでは組込まれていないと思うので、自力でffmpegをbuildするのが一番手っ取り早いです。
　ビルドしたら後は

ffmpeg -i 入力動画ファイル -vcodec mpeg4 -b 64k -s qcif -r 15 -acodec libamr_nb -ab 12200 -ar 8000 -ac 1 -flags bitexact 出力ファイル名.3gp2

とでもすればOKです。

youtubeやニコニコ動画をダウンロードして簡単にデータコンバートしてくれる、firefox用の物があるようです。
私もやってみましたが簡単でしたよ。以下のサイトに書いてありました。

http://bj-linux.blogspot.com/

superbeginnerさんの携帯のキャリアがどこか判りませんが、一般的なドコモ・ａｕ・ＳＢの場合。

ドコモ＆ＳＢは3gpに変換でおｋです。
私はＳＢを使っていますが、再生時間２５分の動画(23MB)の再生を確認しています。
なのでサイズはあまり気にしなくていいと思います。

ａｕの場合は3g2という別規格なので3gpは再生できません。
3g2に変換しても(オフィシャルの動画を売りたいので)サイズ機制が厳しい。
100KB〜150KBが限界と記憶しています。

ウィルコムその他の携帯は判りません。

なのでａｕの場合は
1.諦める。
2.Winで変換。
3.オンライン変換を探す。
以上になりますが3g2に変換してくれるサイトは記憶に無いので、実質１か２になると思います。

ubuntu環境下では未実行なのですが、Windows環境下では3gpへ動画変換した事が有ります。
そこで、Wine(Windowsエミュレイター）を使うとWindows Softwareを動作させる事が可能だ！と言う
知識だけですが有ります。
私も初心者なので目的のFreeware soft(オールマイティ動画変換ソフトで”Format Factory” 以降FFで省略Ver1.85)
が動作すればとても簡単に変換可能です。
因みに、私の携帯はSoftbankで機種はSharp  920SHです。3gp2対応機種です。
DLした動画やDVD-Videoからの動画を再生出来ています。
尚、このFFは音楽も変換可能です。