I tried mine today As well. 1st time in a while. 1st I tried on batman game. Worked for a second then turned off. Now icon is totally gone. It's there for music and pictures. That's it. I have apple tv2 and 4s. Haven't tried on my new iPad.
Finally Fixed the Problem !
I was struggling with this problem on the new iPad with ATV2. I updated my iOS today to 5.1.1 and ATV2 to 5.0.1, which supposedly has the fix for this problem of Airplay not working. Previously I had tried all the fixes mentioned in the forum above i.e. restoring ATV2 software, restoring iPad, turning off Bluetooth, but nothing seemed to help.
Even after the upgrade and restarting my iPad and ATV multiple times today, it didn't help. Finally, I did something I hadn't tried all along is Powering OFF my Router and then Powering it ON, it fixed everything ! Life is GOOD now.
Thanks for all the tips people, hope this helps somebody who is struggling with a similar problem.
Good luck !
No restarting of all devices, No iOS update required.
I had the same issue.
Go to > Settings > Music > under "Home Sharing" > enter your username/password of your apple account.
BOOM! Right next minute problem is resolved. Hope you all enjoy airplay as much as i do.