ファイルマネージャの pcmanfm を使うと多分お望みのことが出来ると思います。
作ったショートカット上で右クリックして名前の変更を選択すると、リアル？のファイル名(〜.desktop)が表示されているので、好みの名前に変更して OK をクリックすれば変更されます。インターネットショートカット名は、〜へのリンクのまま変わりません。そういう挙動で良いんですよね？
もし、ショートカットの表示名も変えたいんであれば、実際のショートカット上(ファイルマネージャを通してではなく)で名前の変更をしてください。

でも、そんなにたくさんショートカットを作って何につかってるんでしょう‥・？
もし、USB メモリなどに入れて持ち歩き用とかであれば、firefox のブックマークの管理でインポートとバックアップから HTML としてエクスポート出来たりしますが、それじゃやな感じですか？

Hideki999 さん による投稿:

で、もしかしてpcmanfmって、今のnautilusと排他関係すか？(汗)  戻すのに手間取るとか、、、、ちと調べたらそんな話題を目に、、、

いや、そんなことはないと思うっすが･･･。どっちも問題なく使えてますんで。
もともと LXDE かなんかのファイルマネージャなので、
$ sudo apt-get install pcmanfm
とすれば、依存関係も同時にインストールされます。

なるほど、確かにアプリの関連付けには若干問題があるようですね。
でも、リンク先の場合、WindowMaker と Gnome 行ったり来たりしてたら‥・と言うような状況ですよね。
おっと、誰かと思ったらトピ主は kiyoshi さんじゃございませんか。
ファイル名の変更などにだけ使う分には問題ないでしょう。