AirPlayで音楽や画面を飛ばす側と、それを受ける側の機器は同一のWi-Fiに繋がっている必要があります。 まちがって隣の家のWi-Fiに繋がってたりしませんか? 「そんなまさか...」と思ってもたまにあります。確認してみてください。
AirMac Express等で5GHzと2.4GHzが別SSID名になっている場合がありますが、あれは同じセグメントなのでOKです。
Windowsなんか使うからです。ファイヤーウォールを一時的に無効にして認識するようならそれが原因です。無効にしっぱなしにしたらWindowsの場合は危険ですので、一時的に無効にするだけにしましょう。有効にしてAirPlayやiTunesのremoteが使うポートだけ通すように設定すればOKです。
Wi-Fiルーターは、バッファローとアイオーデータとNECとコレガとロジテックとプラネックスだけは買ってはいけません!
アイオーデータでは同じ機能を『ポートセパレイター』と呼んでいます。つまりそのWi-Fiルーターに接続している機器同士の通信をさせない(ピアtoピア通信の禁止)機能です。 その状態じゃあAirPlayできるわけないですよね。
その他、妨害電波が出ていることや、その他の原因もありますが、ほとんど上の3つのどれかです。