I had a chance to email with the developer of RockOn. I got a bit of insight from it.
First off, the RockOn everyone sees in the Market is out of date. There's a newer one. The name of it is ³ (that's a superscript 3) but it also goes by RockOnNextGeneration.
Both forms of RockOn use some parts of last.fm, and from what I understand, the album art capabilities of last.fm are mixed with the album art capabilities of the default Android music app.
This is what happens (usually): RockOn shows no Album Art until you tell it to look for album art. First it looks online. If the Album Art online is of higher quality than the embedded album art (higher resolution) it will use that art. If not, then the Album Art embedded in the music file (which is the art you see when you use the standard Music App) is used.
I emailed back and forth with the guy and we discussed how this method doesn't work well. He said it is a good idea in future releases to include the choice to only use embedded Album Art as opposed to online art.
Also, if you check out the RockOnNextGen whatever ³, you'll notice that it has a smoother GUI, although I personally think it looks less cool. The developer said he plans to implement the original RockOn GUI in the newer application eventually, which should mean an awesome looking and easy to use app in the end.