HFS has to cache the file directories I think, if you are testing with your 500mhz fileserver... cpu, hdd speed, ram, and the various clock speeds could be the blame here. Basically the slower the system is the longer it takes for HFS to get the information needed.
I just did a test with a FAIR amount of songs 32gb ... and it works fine on my machine, 2.2ghz AMD Athlon 3500+, 2gb ram, SATA Hard Drives