My daughter has a Nano ipod. Sometimes, like just now, she syncs with iTunes and it will randomly remove a ton of songs from the ipod.
Once or twice it removed all of Beyonce's songs! She said it is not always artist specific, but sometimes.
Anyone have any ideas?