I guess "a reboot" might have been a little ambiguous, but I meant that I restarted OS X (10.8.5, iTunes 11.1, iPad on 5.1.1, iPhone 3Gs on 6.1.3, iPhone 5s (originally not showing up) on 7.0.2).
Prior to that I had rebooted the iPhone 5s a couple of times, connected via cable and toggled WiFi sync settings a few times, restarted iTunes a few times, attempted to "Sync Now" from the iPhone 5s (connected to power and not) a few times. None of these actions had any apparent effect.
I also renamed the iPhone 5s, which originally had the same name as the 3Gs, but that didn't appear to make any difference either, and probably isn't at all problematic, nor is it part of your scenario.
The only other thing I did that might have been related was to assign the iPhone 5s a DHCP reservation on the router, which the other devices already had, effectively giving it a fixed IP. But, even that appeared to make no difference. It was only after I restarted OS X that it showed up. The iPad showed up first, and fairly quickly, the iPhone 5s, finally, after a delay of maybe a minute or more.
The OS X restart was almost certainly the first restart after installing iTunes 11.1, so it's possible the install wasn't able to take care of everything it needed to w/o the restart.
Your "Automatically sync..." option is probably disabled because you have the "Prevent iPods, iPhones and iPads from syncing automatically" option (iTunes Preferences/Devices) turned on. My "Prevent..." option is unchecked and "Automatically sync..." is checked, as well as having "Sync ... over WiFi" checked.