Status update again: Well this is embaressing, I think formatting must have did the trick. Somehow the player totally voided that album name, it wouldn't accept anything of the name of the album. The album name was "... Magni Blandinn Ok Megintir". So I took the dots out of it. Suddenly, all the new files I put on it were there, including that album.
So for anyone who has this strange problem: Format it, rename the troublesome album, re-add all your files and it will work.
I'll have to call Samsung tomorrow and cancel the repair.