By any chance, did the new out-of-the-box player happen to have some tunes and playlists on it already? Perhaps some playlists named "Artists", "Genres", etc.? And when you put your stuff on the player, you deleted those playlists?