Yes turning wifi off on on works, but you'll need to repeat that action often.
We have several devices in family.
I have one iPhone 4S that is now never seen. Have to hard wire that one to sync. Don't think it'll ever be seen otherwise again.
Have one iPad 2 that always has worked without any effort at all (hope saying that wont screw it up). And note all settings are the same as the others. Why it works as designed is just a miracle all it's own.
All the rest I check every few days to verify they're still connected. And of course if I have to reboot usually have to uncheck recheck for every one (but iPad 2) for them to work.
Oh and yes, occasionally have to reboot devices for the wifi uncheck recheck to work.
Or restart iTunes. Or restart computer.
Fun times. 8-/