Hello,
I have a Z120BT with this same issue. I used mediamonkey to load the tracks on a brand new 160gb Classic. Album art works just fine, but the letter search doesn't. Is there a solution that anyone knows of? Thanks in advance.
*Edit* I loaded itunes and connected the ipod. Played a couple tunes while it was connected, and ejected it. It now works properly.