USBメモリーに、ブートセクターがちゃんと入っていない様な気がします。ファイルがちゃんと有っても、ブート領域までは見られません。
試しにもう一度、USBメモリーをフォーマットして、インストールし直してみる事をお勧めします。

また、10.04のデスクトップ版の入ったPCがあるなら、システム＞システム管理＞スタートアップ・ディスクの作成 で作ってみるのも良いかも知れません。
isoファイルを指定出来るので、コピー又は再ダウンロードでサーバー版のisoファイルを入れれば、サーバー版のUSBメモリーも作成出来ます。

＞USBからのブートだとDVDを消費しなくて済むという点がいいですよね。
これは自分も同意見です。だから今回の10.04からは自分も、スタートアップ・ディスクの作成 で、USBメモリーからインストしてます。

追記です。
https://help.ubuntu.com/community/Installation/FromUSBStick より、
システム＞システム管理＞スタートアップ・ディスクの作成 で、任意のisoイメージを指定できる様にするには、usb-creator パッケージを入れないといけないかも知れません。

システム＞システム管理＞Synapticパッケージ・マネージャーで、入れてみて下さい。