Rhythmbox not saving the album art permanently
As far as I know, the Plugin isn't working at all because the Site where the Covers can be found has decided to disable Rhythmbox-Users completly because of too high traffic.
What you can do is searching your Covers manually via images.google.com, save them as folder.jpg in the album-folders and (if you want) inject the Artwork into your .mp3-files with a Tag-Editor like Mp3Tag (works fine with Wine).