iTunes no longer stores the album art in the mp3's, they have special folders with the files that include linking information for each individual song. This is supposed to save space as one image can be linked to multiple songs instead of each song having the image stored within it. Unfortunately, these images cannot be edited or moved outside of iTunes.
However, I do believe some of my mp3s might be old enough to have such embeds, so the program you mentioned may work for a percentage of my collection. I'll give it a try.