Another thing to check is the tag version. Sansas work best with ID3v2.3 ISO 8859-1. MP3Tag lets you set which version it writes, so check there and resave the tags if you change the setting.
(I don’t know that different tag versions will cause the problem you’re experiencing, but it can’t hurt to update your tags to what the player likes best.)
