Comment 9 for bug 229197

It appears cover art is only shown on tracks of which you have already seen the coverart. Tracks where rhythmbox has already "installed" the coverart. It doesn't matter whether the covers are stored locally or in ~/.cache/rhythmbox/covers.

Rip a new cd to you library, add the coverart to the folder or let rhythmbox download it by playing the first track. Confirm you see the coverart in rhythmbox. Now play track 3 in rhythmbox (don't play track 2). Rhythmbox will show the coverart.
Play the first track again and iconify rhythmbox so the notifications will show. Sit back and watch (and listen ;-)).
When track 2 starts you'll see no cover art, but when track 3 starts you will.

Note: you don't have to view the coverart in the main rhythmbox window to "install" the icon, hovering your mouse over the rhythmbox icon and viewing the popup works as well.
(when track 4 starts you'll see no coverart in the notification, hover over the rhythmbox icon and you'll see the cover in the popup. Rightclick and choose "previous" (or use a mediakey on your keyboard) and wait 'till track 3 finishes: the notification for track 4 will now show the coverart)

I hope this helps track down the bug,

Tibault