This problem has just started happenning to me recently. I usually create a playlist in iTunes and sort by track number. And Apple TV always kept to the sort order for the playlist. I try to do this now and the songs come up in a random order on Apple TV(I tried deleting and redoing twice) even though I have the column for track # set for sorting. Any ideas?