As noted in Reply #13, the Jukebox Licence Office (J.L.O.) license, as of January 2007, is no longer usable for any jukeboxes containing hard drive storage media.
Hard drive based jukeboxes now require individual licensing from ASCAP, BMI & SESAC separately, and, only if you install music from artists which are members of any one of (or any/all of) the "PROs" (Performing Rights Organizations). All three PROs have a search function on their web sites so you can see which artists and which songs they represent. If your artist and song/s are not listed by any of the three, you would need to negotiate licensing with the copyright holder of each song individually. (not likely to happen)
The new "Digital Jukebox" licenses (which, yes, is a totally incorrect reference, since CD's are digital too) available from ASCAP & BMI also require submission of quarterly "Use Reports", basically popularity meters and song ID information, which they use to determine how to split up the license fees to the artists. Also these licenses do not cover jukeboxes with Internet connections, they must be stand alone. e-Cast, AMI & Touchtunes currently have the only "Digital Jukebox" license which covers Internet connected jukes in the USA. Mainly due to security of the music. It must be encrypted even on the jukebox's drive to prevent unauthorized accessing of the music.
There's no point in arguing how fair and how costly licensing may or not be simply because it IS federal copyright law. (not just in the USA either, most commercial jukeboxes around the world require similar licensing) While you might, for a short time, operate a jukebox commercially without licensing, you will eventually be caught. If not by ASCAP or BMI's on-going investigations, another near by 'location' (business with a jukebox that is paying for licensing), local jukebox operators, a disgruntled patron, and even some DJ's WILL turn you in!
Checking local & state laws is also important. While these will not be copyright licenses, some areas do have a tax or some fee (what ever they call it) on coin operated equipment in general. In some cases a local or state jukebox fee will be less than a video or pinball game.
Another issue of commercial use is of course, copying. Since the above mentioned licensing says they can't be connected to the Internet, you effectively can't get music into the jukebox with out some form of copying. Don't fool yourself, ripping CDs is a copy! While this may be over looked for personal use, commercially it may not! The only solution here is to buy MP3s from sites like Amazon or Wallmart, save them directly to an external flash or other storage media, (something that can't in itself play the music) and when you install the music into the jukebox, the jukebox software must automatically do a 'move' not a copy (yes, there is a difference) from the portable media to insure there is no copy of the song file/s left behind. Sure, that's all a matter of trust, but at upwards of $10,000 fine per-song, it's best to comply! Remember, the required "Use Report" contains song IDs, copying could be traced. While both Amazon and Wallmart (and most other on-line music sources) specifically state for personal use, or non-commercial use, the PROs licensing covers that. Officially that's what their for, commercial use of non-commercial use music.
USA copyright law can be found here:
http://www.copyright.gov/title17/