Ok, I finally got mine to display your message. I left it on random play for about 20 hours w/my amp turned off. And after it displayed that message, the program didn't hang but just had an empty queue. I think I might possibly know of an idea of what conceiveably is happening.

I think the program marks each random song that is played as being played and does not re-play them for a given random set. I don't recall ever hearing the same song twice when I'm set to random, and that's 90% of the time I use my juke. So possibly you're just exhausting your library, and it may not be a bug at all. When you turn random mode off and back on, it resets all played songs and begins fresh. Just a thought, but it feels right. Cyberpunk can probably confirm or deny this. Spend a couple weeks ripping every cd you have, and the problem will probably take longer and longer to pop up.
For the album spacing getting messed up I think if you create 2-3 empty albums and adding/removing them as needed to keep the screen full will fix this. I haven't tried it, but again it feels like it should work. The different listings during random mode... I think we're stuck with it at least until the next version.
With the little quirks and bugs, it's still more than worth the $15 I spent(registed about 2 weeks before the increase). It brought my entire project together in one fell swoop. I was using arcade jukebox v.7 and built my control panel around it. But after you get 100 songs on it, it's not very usable. Get 1200+ songs on it and you'll never find what you want. Works great for singles, not so much for full cd's. So I still need to redo my cp, but it's working well. I didn't go the pc speaker route. I've got monster speakers and good power so it SOUNDS like a juke, shakes the walls and windows. My cab looks more like a kiosk than a jukebox, but once I find a gutted juke cab that will be taken care of.