It is with stratospheric disappointment that I found out in these forums that the Clip+ devices firmware (and others, apparently) don’t support Unicode. Apparently we need to travel in time and get back the tags in ISO-8859-1 encoding. Or just use Rockbox. Since I didn’t want my kids heads to explode with Rockbox just yet (the amount of features is a bit much IMO), I opted to fix the tags.
Another option would be for SanDisk to publish the code to their firmware and develop it as a freely-licensed open source project. I am new in these forums, I suppose this may have been discussed (or even announced) before but I didn’t find any reference.
For those of you using GNU/Linux I found a great utility for editing tags. Your distribution should have the “easytag” package, which let me save the tags with the appropriate encoding, and also fix some artists / titles that were mixed up.