And all for nothing - none of my Android devices have ever restored my wifi passwords, it is always a mission to find and input my password on a fresh phone.
My wife recently picked up an S4 and none of her things synchronized. I was pretty surprised at the time but thinking about it later I realized the AT&T clerk skipped the initial sign-in process. It looks like the option to sync old apps/passwords is only available upon launching a fresh device (which being a Nexus user no clerk ever bypasses setup on my devices).
Anyway, this might be why your phone isn't syncing? I'd be interested in seeing some option to force sync Android devices with backed up data at any time.