I was able to get my Apple TV working again by downgrading the firmware following the instructions in this message:
https://discussions.apple.com/thread/4387125?answerId=20008613022#20008613022
In case that message disappears, here's my translation:
1. Connect your Apple TV to your computer via USB. Don't plug in the power cable.
2. Download the older 5.0.2 firmware from Apple here:
5.0.2 (Apple TV 2): AppleTV2,1_5.0.2_9B830_Restore.ipsw
5.0.2 (Apple TV 3): AppleTV3,1_5.0.2_9B830_Restore.ipsw
3. Open iTunes and select the Apple TV. Hold down the option key and press the restore button at the same time.
4. In the dialog that opens select the firmware that you downloaded.
5. The restore process will take a few minutes. Once it's done plug your Apple TV back into your TV. If the date and time message persists just press the menu button to skip it. This got mine working again.