Here's my guess on the problem: Many people create a playlist pointing to the songs on their computer. Since he's using iTunes to create the playlist, my wager is the playlist is indexing the songs on his computer, and points to actual filenames, while the files on his iPod have been synced with iTunes and have the crazily renamed filenames.
My suggestion would be to either create the playlists in Rockbox, or not use iTunes to sync your songs, and make sure to create the playlists pointing to the copies of the songs on the player, not on the computer. (Assuming my guess here is correct.)