I suggest you try again using this app, but this time make sure you're following these steps:
Load it up, click File/Change directory (up the top left) then select the folder where all your local music is stored for spotify.
Go through the list to the songs you want to play on spotify and make sure the image file (will pop up on the meta data list on the left) is visible. Then manually upload a new album image file and save it. Tip: get the image file to be no larger than 300x300.
Basically just run mp3tag and fiddle with it and it should work. Maybe it's a question of trial and error. Just make sure after you've made the changes, you right click on the song in the list and click 'save tag'.
Hope this helps!
Help others find this answer and click "Accept as Solution".
If you appreciate my answer, maybe give me a Like.