Can you check the Apple TV SW you are using? Subtitles over AirPlay will require Apple TV 5.1 or later.
Also, depending on your Apple TV’s settings you may need to toggle on subtitles using the remote. This can easily be done by holding the center (select) button on the Apple TV remote (while AirPlay is active) and select the desired subtitle track.
Thanks, James! Yes, you were right. I had 5.0 (which was non-upgradeable due to ATVFlash). Did a factory restore and upgraded, so now subtitles are working.