Can you be a bit more specific? Is there a certain player you're finding this in? Are you certain your MP3 files are properly tagged and the right album art is not thumbnailed by Windows?
Spotify does have some issues currently (not sure if the stable build, but the beta does, and it's on their release notes) and they're trying to iron them out. For local files, as long as the file is properly tagged (the tag should be a part of the file, not just a folder image) it should work.
For checking tags and modifying them I suggest to use MediaMonkey on a PC.