別のユーザーだと始めからついてるみたいです。Gnomeです。

 同じバージョンのUbuntuのCDでは起動した場合はアプレットは表示されますよね？表示されないのであれば機械的におかしくなったと考えられます。

 新しいユーザーを作成してもアプレットが表示されないという事なのでユーザー設定等をバックアップして再度インストールし直してみるのが良いかと思います。プログラムを再度入れ直す際、依存関係により削除されるパッケージが発生するのであればそれが原因ではないかと思いますのでプログラムの追加の時に注意してシステムの再構築を行えば良いんじゃないでしょうか。

 ちなみに試しに自分の環境でただnmアプレットをパネルから削除しただけであればシステム→設定→自動起動するアプリを起動し、追加(A)をクリック、名前の欄にネットワークマネージャー、コマンドの欄は
nm-applet --sm-disable
説明の欄はネットワークマネージャーと入力してみて再起動すれば復活はしました。ただし、私の場合は新しいユーザーを作成した場合、アプレットは表示されていましたのでlepuserさんの状況とは異なりますが…。