Assuming this is not the first time you have used your Apple TV
- You might try restarting the Apple TV by removing ALL the cables for 30 seconds.
- Also try restarting the router.
- If the problem persists, try a restore, you may want to try the previous procedures several times before doing this.
- If restoring from the Apple TV doesn't help, try restoring from iTunes using a USB cable.
If this is a new Apple TV, in addition to trying the above, it may also be that your network router is not allowing access to the timeserver, check that your router allows access over port 123.