http://support.apple.com/kb/TS1741

does this help?

you do have it allowed for iTunes to "Look for remote iPhones of iPod Touch" right? (stupid question but it has to be asked)

the issue the link points out is the firewall settings cannot be set specifically to "Allow essential services only"

---