このページも事前に確認しましたが、これはエンコードについてですよね？
動画を一々エンコードして見るのは面倒なので、Adaptive Multi Rate (AMR) デコーダーというプラグインを入れてTotem等で見れるようになりたいのですが…。
無理でしょうか？

ありがとうございます。
参考URL先に書いてある「Any Ubuntu Release and keyring: 」の部分の通り端末で

$ sudo wget http://www.medibuntu.org/sources.list.d/`lsb_release -cs`.list --output-document=/etc/apt/sources.list.d/medibuntu.list; sudo apt-get -q update; sudo apt-get --yes -q --allow-unauthenticated install medibuntu-keyring; sudo apt-get -q update

とした結果、

W: GPG error: http://ppa.launchpad.net jaunty Release: 公開鍵を利用できないため、以下の署名は検証できませんでした: NO_PUBKEY 6AF0E1940624A220
W: これらの問題を解決するためには apt-get update を実行する必要があるかもしれません

と言われました。そこで

$ sudo apt-get update

としたところ、また同じように

W: GPG error: http://ppa.launchpad.net jaunty Release: 公開鍵を利用できないため、以下の署名は検証できませんでした: NO_PUBKEY 6AF0E1940624A220
W: これらの問題を解決するためには apt-get update を実行する必要があるかもしれません

と言われてしまいました。そこでグーグルで鍵を入れる方法を調べて

# gpg --keyserver pgp.nic.ad.jp --recv-keys 6AF0E1940624A220

と打ち込んでみましたが

gpg: 鍵0624A220をhkpからサーバーpgp.nic.ad.jpに要求
gpgkeys: key 6AF0E1940624A220 not found on keyserver
gpg: 有効なOpenPGPデータが見つかりません。
gpg: 処理数の合計: 0

という風に、鍵が使えません。
もしかしたら以下のURLの通りLaunchpadの問題かと思い、設定の修正を自動で行ってくれるスクリプトというのを実行しました。
http://ubuntu.studiomohawk.com/400/quickpost-gpg-error-ppalaunchpadnet-intrepid-release/

スクリプトを実行した結果は以下の通りです。

# sudo ./launchpad-update intrepid
Release: intrepid
Please Wait...
cat: keyss: No such file or directory
rm: `keyss' を削除できません。: No such file or directory

どうもlaunchpadの問題ではないようです。
なぜ鍵が利用できないのでしょうか？

ええ。それも同じく

W: GPG error: http://ppa.launchpad.net jaunty Release: 公開鍵を利用できないため、以下の署名は検証できませんでした: NO_PUBKEY 6AF0E1940624A220
W: これらの問題を解決するためには apt-get update を実行する必要があるかもしれません

と表示され、apt-get updateしても解決しませんでした。

言われた通りlaunchpadを無効にした結果、問題なくリポジトリやamrを導入できました。ありがとうございます。

しかし相変わらず3gp形式の物に対してTotemではamrを認識してくれないのか、amrを検索しだして「要求されたプラグインを含むパッケージは見つかりませんでした」と言われます。
そして音声はなりません。
MPlayer、SMPlayer、VLC media playerどれを試してもコーデックが無いためか音声はなりませんでした。

諦めるべきでしょうか。

動画探して確認しました。
（環境 Ubuntu9.04 AMD64/i386 デスクトップ版ともに）
smplayer　○
vlc,totem　×
VLCは、samrはサポートして無い旨メッセージが出る

なので、smplayerを確認してみてください。
（これだと、mplayerでも音出そうですが？）

mplayer のリリースノート見ました。
バージョン 1.0-rc2から、ffmpegのパッチ不要で、amrライブラリを使って、3gp 再生できるようになったとか何とか書いてましたよ。
（英語力は定かでないので自信無し）
確かに、mplayerでも、音出ました。
ちなみに、私の使っているバージョンは場合
　mplayer　2:1.0~rc2-0ubuntu1
　smplayer　0.6.6-0ubuntu1
　libamrnb3　7.0.0.2-0.1medibuntu1
　libamrwb3　7.0.0.3-0.0medibuntu1
です（多分、Ubuntu9.04 最新状態）。

####
試しに、Fedora11（x86_64）で再生してみましたが、音出ませんでした。
ライブラリ類は入ってますが、mplayerが、1.0-0.109.20090329svnという、よく分からないものです。
####