General :: Cloning Android To Identical Devices?

I have purchased 3 Samsung Galaxy Nexus devices for my family, and one for myself. I wanted to setup all our devices for them and pre-install essential apps for them, and lay it out in a way which makes each device identical so that my family (which is new to Android) can all get the same easy experience from their devices, rather than everyone getting a different LG/Samsung/HTC device and having to deal with differences in skins every time someone phones me with a question about their device.

Here is what I have done:

1. Unlocked bootloader, root, installed CM10.1.2 + gapps onto my own personal device. Clean install, wiped everything.

2. Setup android with a temporary Gmail account, installed about 20 apps, setup the homescreen, changed a few settings for simplicity, change wallpapers, etc.

3. Once I was satisfied, I removed the google account, rebooted to recovery (CWM 6.0.3.2) and made a Nandroid backup which was later copied to my home server.

4. Unlocked Bootloader, rooted and installed CM10.1.2 + gapps on all the other devices, booted the device then transferred the Nandroid backup from my home server to each of these other three devices. Restore the backup, reboot, all seems fine so I setup new individual google accounts, and away I went. Everything works fine, at least so it seems.

Now the issue is that I'm having came a day or two after I got everything setup on each device. At the moment I'm having serious issues with the Google Play Store and Push Notifications. Almost all devices intermittently have issues with this. The play store issue I'm getting is [RPC:S-5:AEC-0], and prevents me from downloading or updating apps. Push notifications is not working either. For example, Google hangouts notifications don't notify me of messages on devices intermittently unless I manually check the app. Same goes with facebook and snapchat notifications. Very annoying. Tried all sorts of fixes such as removing the Google account, rebooting and adding it again, but no luck.

I changed the Android ID on each device hoping that would work, but still no luck.

Edit: Tried making a titanium backup of one device and moved it to a rooted Galaxy S2 running CM10.1 nightlies, and no such issue. Also, updated one nexus device to the latest nightly, still no fix.