I know this is old but I just had this very problem, and wanted to share how I solved it. I had bought a new ATV3 and took the old ATV2 and installed it with a small tv in another room. I plugged everything in and started it up -- and couldn't get past Setting Time and Date. The remote would not stop it from trying to do this, either! I.e., pressing "menu" had no effect. Then I realized that I was trying to use the NEW remote control on the OLD ATV2 -- and as soon as I got the OLD remote control from the other room and used it, I was able to stop the processing and finish the installation successfully. I had assumed the remotes were the same because I had successfully used the OLD remote to set up the NEW ATV3. Weird. But now I know, and so do you.
(Another weird thing: now that the old ATV2 is in the same room as my iMac, I've noticed that when I use the remote to control the ATV2, the iMac on the other side of the room responds: it wakes up, starts playing sound recordings, etc. Oh well.)
I had similar problem, and made a new discussion (https://discussions.apple.com/message/23188967#23188967) before seeing this thread.
After reading through here, I tried the "no ethernet cable", and it not only worked...
But it worked without a router / airport express!!!