I've just solved this issue on my 'Live with Walkman' after some tinkering.
The Walkman app assigns one cover per album of songs. I just changed my album names on mp3s that weren't tagged and covers are ok now.
Having empty album tags in mp3s will put all songs in an album named as the folder they're in, which means they will most likely have some random cover picked out from one of the mp3s.
One issue remains still: refreshing (changing) album art on some songs. Delete, power off/on, re-upload mp3 worked for me.