Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
The Zune HD has alphabet search. Apparently the OP never noticed. Music>Songs> Tap an icon to bring up the alphabet, then tap U (or Z) to jump to all the songs beginning with U (or Z), or if none exist then the next closest letter among your songs.

The Touch does a fine job too. Either device is great.

The Zune HD does indeed have a search function (letter search) which is really handy. If the OP returned the Zune HD because of this, it's kind of ironic. :D
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.