Hi.
In regard to your question, " If it doesn't work on iOS 5, then it shouldn't be in the store for iOS 5 devices. Right?"
The apps general purpose is to enable you to view content on the device. AirPlay compatibility is a secondary feature and was only recently added in Feb this year. So, making the app available to iOS 5 users makes sense.
The post I read specifically mentioned the problem of hearing audio but not seeing video via AirPlay that was resolved by upgrading the devices to iOS 6.
Unfortunately I ran across this thread while going through the Apple forums here trying to resolve the issue of the Airplay button suddenly not being available on any of my devices (a router reboot was the resolution btw). It was a pretty common result of every google search I tried so it shouldn't be hard to find.
I understand your hesitation to upgrade to iOS 6. I've held at 6.0 myself, which works fine, but 6.1 and 6.2 seem more trouble than benefit.