Folks, I was having the exact same problems. I tried everything mentioned here, including a complete restore of my iOS devices, but nothing would work permanently. It would work for a few minutes or hours, but then the problems re-surfaced. I'm not sure that the root of our problems is the same for each of us, but I permanently solved my problem. To check if your problem is the same as mine, (on a Mac) open up the terminal and type:
scutil --get HostName
If it comes back with "Hostname: not set" then very possibly you have the same problem as I did. It's important to note that HostName is different from ComputerName, LocalHostName, and DHCP Client ID, so don't assume you've got a host name set because your router shows it, or system preferences shows it.
When you plug it in, the iOS device searches for a Mac with the host name (in my case) Fabio-Papas-iMac on the network. If the hostname isn't set, then it doesn't find the Mac, and can't sync to it. To fix that, go back to terminal and type:
scutil --set Hostname "Fabio-Papas-iMac"
or whatever the equivalent is for you. You can find out what host name your iOS device is looking for by going to Settings-> General -> iTunes Wi-Fi Sync. It tells you there. Once you've done this, you must reboot. Then go into iTunes and watch your devices automagically sync. If they don't, plug them in and make sure that wi-fi sync is enabled.
Here's what I'm thinking caused the problem. The wi-fi syncing communication is all done IP to IP and NOT via host name. But since IP addresses can change, wi-fi sync uses the hostname to find out what your Mac's IP address is. The iOS device then stores this IP address and uses it for syncing for a while, until an internal timeout tells it to find the Mac by host name again to make sure it still has the correct IP. If the host name isn't set, the sync doesn't work. We would plug the iPhone back into the computer (or do a restore, etc.), which would once again store the IP address in the iOS device, which would make wi-fi sync work again, and after the timeout period, the problem would just happen again. I think that in iOS 5.x, this timeout period was much longer. Maybe weeks. In iOS 5, once in a while I would notice that this problem would start, but just simply re-syncing via cable would fix the problem; at least for a long while. With iOS 6, i think they shortened this period to a few hours. I'm not sure why some of us do not have a host name set. I'm a web developer and use my Mac to run and test web apps. It could be that I (or a program I use) cleared out my host name by accident.
Hope this works for all of you, and happy syncing!