I spent 2 days trying to get this to work. The manual isn't really clear on things but after reinstalling itunes (not necessary) and resetting apple tv (not necessary), here is what I did.
1. I use tiger. I went into the firewall setting. Selected itunes music sharing. Hit edit and you will see UDP port empty. It won't let you add port 5353. The help section at apple states to have this port open. I created a new one with the same name (case sensitive) and added the UDP port number along with what was in the other one. It will over write the old one which is why you type it EXACTLY the same. I am not 100% sure this was the cause because of other things I missed but think it is.
2. Log onto itunes and connect to the store. Do not disconnect.
3. On the apple tv, Do not let it automatically set up your wireless. Do it manually and its case sensitive for the name of your wireless router. Input your password. When it states its done, go to the source section.
4. I selected to sync at first so it would show up in itunes. Since I prefered to stream, I backed out and selected itunes. It will disappear and come back. (make sure you have look for apple tv selected).
5. Fill in the code and wholla, i'm in.
I did some testing by closing my wireless link to see what would happen and yep, apple tv dies. Its streams through the router which isn't really clear in the book about this. Bottom line is insure your wireless network is hooked up properly on the apple tv AND your hooked up live with itunes store. Again, not really sure about the UDP port but the help section at apple states to make sure this port it open. I actually tried shutting off my firewall and doing this and it did not work. Hope this helps.
Randy