You should see a message saying "Dir buffer full" when you start the jukebox. Are you running Rockbox?
You should really consider sorting your collection in subdirectories.
If you still want to have huge amounts of files in a single directory, go to Menu-General Settings->System->Limits->Max files in dir browser and set it to a suitable amount. This will take away some of the MP3 playback buffer and use it for file name cache instead, which will reduce the battery life somewhat.