I've found that the Pilot works well using ID3v2.3 and UTF-16 encoding. My Ubuntu box (and likely most Unices) threw fits with UTF-16, much preferring UTF-8. Microsoft seems to like UTF-16, though, and the Pilot being a P4S device... I'm sure MS says UTF-16 must be supported. On Windows, I use the outstanding MP3Tag to first remove ID3v1 tags, then I convert ID3v2.4 UTF-8 (as written in fb2k) to ID3v2.3 UTF-16. I also use MP3Tag to do my album art embedding. I've found that with this combination, the Pilot is quite adept at displaying a variety of European character sets (even Estonian and Hungarian)... I think Cyrillic as well, but I don't recall.
That said, my main desktop is WinXP, so I'm not sure the best tools to use in Kubuntu... perhaps mp3tag will work in Wine?