I finally gave AllofMP3 a test run this past weekend while down in L.A. AllofMP3 is a new online music service based out of Russia but offering an option to view its site in English (albeit with a few humorous translations).
It took a few hours before I could get through--the site claimed to be down for technical upgrades. When I did, I was prompted to sign up for a V.I.P account before I could begin purchasing music. That simply means loading a payment account with funds to minimize AllofMP3's transaction costs. What you purchase is bandwidth for downloading the songs at the rate of $10 per 1 GB in increments of $10, $15, $25, or $50 for 1GB to 5GB.
A music service based out of Russia? A bit dodgy, but they offered PayPal as a payment option so I chose that in order to keep my credit card number out of their hands. After loading up $15 and 1.5 GB, I browsed the music catalog (they also offer a music video and Russian music catalog).
The selection is not great, but it includes just enough interesting titles to offer at least 1 GB of appealing music. Once you select a song you want, you need to select what format you want to download it in. You can also choose to have it encoded straight from the source CD which costs slightly more. The mind-boggling array of formats offered, including those that aren't locked by DRM restrictions, is one of the primary breakthroughs of the service. Formats offered include:

MP3 in both Lame and Blade codecs, constant and variable bit-rates (CBR and VBR), from 128 kbps to 320 kbps

Windows Media Audio (WMA) 7 or 8 or 9, 128 kbps to 320 kbps, CBR One-Pass or Two-Pass or Quality-Based or Bit-Rate-Based VBR

OGG Vorbis files in CBR from 128 kbps to 320 kbps or Quality-Cased CBR from Q3 through Q10

MPEG-4 AAC in CBR from 128 to 320 kbps or VBR in 4 different quality levels

MusePack MPC files in five different quality levels

Select albums are also available for download in lossless formats, including the original wave files for those simply wishing to download an entire CD.
Once you've bought the songs, you can find links to download them in your download section. Here's where the music purchasing experience using a web browser pales in comparison to using client software like iTunes. You have to right click on each song and select Save As and select a folder to drop the file in. AllofMP3 offers some client software for purchasing music but I wasn't able to try it as it only works with Windows.
Another annoyance is that once you've downloaded the song, it disappears from your download area. Since you're paying for download bandwidth, why not just leave the songs you've purchased in that section but mark them as previously downloaded?
Most of the downloads were available immediately after I purchased the, though a few took a few days before they were ready. If their lawyers can withstand the inevitable legal siege, AllofMP3 needs to go out and buy one of every CD in existence and rip them in every possible format, starting from the most popular albums and formats and working back.
The music? Plays great. I typically have rock encoded at 160 kbps and classical music at 192 kbps, and at those rates, the cost per song is phenomenally low.
My primary question is how they get away with this legally. Not that I'm complaining, but I am curious. In their FAQ, one of the question is just that: is it legal to download music from AllofMP3? The reply:

All the materials in the MediaServices projects are available for distribution through Internet according to license # LS-3?-03-79 of the Russian Multimedia and Internet Society. Under the license terms, MediaServices pays license fees for all the materials subject to the Law of the Russian Federation "On Copyright and Related Rights". All the materials are available solely for personal use and must not be used for further distribution, resale or broadcasting.

Oh, of course. The Russian Multimedia and Internet Society. Russian translators are being hired left and right by the labels to try and decipher that license.
CONCLUSION: AllofMP3 won't cause me to throw away iTunes, but its two primary trump cards--ridiculously low prices and the ability to select any format you want to encrypt the song in--overshadow its warts, of which the largest is its meager selection. We're talking about prices 10X to 20X cheaper than Apple iTunes Music Store. Let's see if they can avoid being sued out of existence by the labels. If so, they should pour some kerosene on the fire.