The listing BUG definitely lies with iTunes 10.6, re-install 10.5.3 and you'll get your list back in order again, even if your Apple TV2 has been updated to 5.0 - Don't spend hours re-importing your Media, it won't help... (See Update below)
From both a cosmetic and ease of use view (ATV5 is horrible) if you can, stay at 4.4.4 as long as you can.
If your one of those many people that are experiencing constant drop outs now while playing from your own Library, just quitting iTunes and restarting it seems to clear the problem for a while at least.
(I use Remote HD (great software) to view the comp screen from my chair to do this as comp is upstairs))
I have also tried the 'set AppleTV2 clock to manual' idea and that has also helped reduce the number of iTunes Library disconnections temporarily.
NB: If you have two Libraries available in the 'Computer' listing if you lose one the other will stay, so that points to a Bonjour error between iTunes and AppleTV2, I've tried setting IP to manual as well and that doesn't seem to solve the problem and downgrading the firmware of Time Capsule/Airport Utility form 7.6.1 back to 7.5.2 loses some functionality.
I don't recall a single problem using the iTunes 10.5.3, AppleTV2 4.4.4 and Airport Utility 7.5.2 Combination on OS 10.6.8.
...Will teach me to upgrade within 6 months of a release!
Update: Although re-installing iTunes 10.5.3 fixed the 'Listings out of order' problem, the disconnections kept happening even after setting the clock to manual etc.
After noticing that when creating a 'New User' on a seperate comp allowed me to play anything, even 1080p, without any droputs, I eventually deleated all the Library files that I had restored using Time Machine and re-built the Library, now I have TV Shows and Movies in order and No drop outs.
Using the iTunes 10.5.3, AppleTV2 5.0 and Airport Utility 7.5.2 Combination on OS 10.6.8.
Do you have any better luck with that if you update to iTunes 10.6.1.7?
From the notes for the release:
iTunes 10.6.1 provides a number of improvements, including:
• Fixes several issues that may cause iTunes to unexpectedly quit while playing videos, changing artwork size in Grid view and syncing photos to devices.
• Addresses an issue where some iTunes interface elements are incorrectly described by VoiceOver and WindowEyes.
• Fixes a problem where iTunes may become unresponsive while syncing iPod nano or iPod shuffle.
• Resolves an ordering problem while browsing TV episodes in your iTunes library on Apple TV.