Here are some steps and notes to try:
MANY people are reporting they've had to try multiple micro USB cables to find one that works. I got one that worked from a neighbor.
For clarification, this needs to be a "micro" USB, not a "mini" USB
Some people have also reported they've had to try the Restore process more than once.
1. Unplug Apple TV and move it to your computer running latest version of iTunes.
2. Quit iTunes if running.
3. Plug micro USB cable to the back of the Apple TV.
4. Power the Apple TV using the AC cable.
5. iTunes shoud either launch itself (a good indication that the micro USB cable you're using is compatible), or launch iTunes.
6. Click Restore. Software will download and install (big file).