どのような手順で無線LANを設定されたのかを先ず書くべきかと思いますが、
ubuntu-desktopをインストールする前=CUIの段階で/etc/interfacesからネットワークの設定を行った場合は、
これが優先されてデスクトップ環境でネットワークの設定を行うNetworkManagerからは設定できない
(「このデバイスは管理されていません」的なメッセージが出たとは思います)
ということはあります。
「インターネット接続が必要なコマンド」が通るとのことなので、
ブラウザでWebページの閲覧とかもできる=インターネット接続自体はまったく問題がないのであれば、
何らかの理由で(上記のものかも知れませんしそうでないかも知れません)、
デスクトップ環境で無線LANの情報にタッチできないという状況が生じている、と考えるのが妥当かと思います。

というわけで、Ubuntu Server 13.10のインストール後からubuntu-desktopのインストールまでの間で、
ネットワーク関連の設定を中心にどのような作業を行ったのかを教えてください。

やはり、wpa_supplicantを使ってらっしゃいましたか。
ただ、その場合でもデスクトップから普通にインターネットは使えるはずなのですがね……。
(「デスクトップ側からはインターネットに接続できていない」の意味がイマイチ取れません……。)

ひとまず、次を試して、ご報告いただけますか?
1) /etc/network/interfacesを下記のものに書き換える。
2) デスクトップのNetworkManagerからネットワークの設定が可能になるのを確認する。
3) ネットワークの設定をする(この段階ではDHCPで)。
4) ブラウザ等で「デスクトップからもインターネットに接続」できることを確認する。
5) DHCPでインターネット接続が可能なことを確認できたら、NetworkManagerから固定IPの設定を行う(手順は下記参照)。

この手順はネットワークの設定をデスクトップ版と同等にするためのもので、5までうまくいけば、
/etc/network/interfacesの設定に何か問題があったか、その設定がデスクトップ側で効いてないか、あたりに問題が絞られそうです。

12.04デスクトップ版の/etc/network/interfaces

auto lo
iface lo inet loopback