I managed to get mine working. The key for me was the Network proxy settings, but here's my entire setup:
These instructions are for OS X, but should have comparable settings in Windows.
_iTunes preferences:_
"*Look for iPhone and iPod touch Remotes*" enabled
"*Share my music*", with "*Require Password*"
I don't think you need either of these settings. However, I mention them here since some people have suggested that you cannot share your library with a password while using Remote.
_System Preferences:_
Security/Firewall set to "*Set access for specific services and applications*", with iTunes added. Use TCP port 3689 and UDP port 5353 if you are using another firewall. See
http://support.apple.com/kb/TS1741
Network/Proxy "*Bypass proxy settings for these Hosts and Domains*".
This was my problem that prevented one of my computers from connecting to Remote. If you have a proxy server, ensure that your local area network is included in this bypass list. For example, if your computer IP Addresses look like 10.0.1.7, 10.0.1.1, 10.0.1.3, etc., you could add 10.0.1.* (you can also use notation like 10.0/16, if you understand it). Without this, your iTunes host will try to access the Remote application via your proxy, and will likely fail or connect intermittently.
Good Luck!