How are the devices connected? I have seen routers that won't let bonjour cross from wireless to ethernet. So if the ATV is connected via ethernet try connecting via wi-fi instead.
It's all wireless.
It just occurred to me that my wife hasn't upgraded from iOS 5 yet on her phone. I should see if it works on hers.
Did you ever find a solution to this problem? I am having the exact same issue and I'm starting to think it's just a software limitation.
No, sorry. If you figure it out please post back here, and I will as well, of course.