If you have a 'cover.jpg' file in your folder for an album, it can not be replaced through the last.fm album cover search feature. Those will download png files, and so you end up with both "cover.jpg" and "cover.png" in the folder. Subsonic isn't looking for the newest, it is looking by name, and in the priority order, cover.jpg comes first.
So it will say 'successfully downloaded', which is true, but continue to show the old cover.
Workaround is to just go into the folder and delete cover.jpg and it will find the new file on the next time you open that directory in Subsonic.
Not a big deal, just can seem surprising.
J