Another idea:
Recently we've created a jukebox on our website. We used the program Coffeecup Webjukebox. It's nothing fancy but it works rather well.
The interface is pretty straightforward and easy in use. You can choose from several skins.
RnAM Jukebox Rob and Anne-Marie
Hey R or AM...
The web site for CoffeeCup
http://www.coffeecup.com/web-jukebox/shows settings that allow SHUFFLE - but there does not appear to be a Shuffle Button on your jukebox. Is that a global settings - set when you create it?
Also... when you add songs, can you add a URL (for example, could you add a song on my site to your list?) or is it just songs from you computer? Do the songs have to all be uploaded to a specific place?