I had a similar problem with notes the other day, try doing this...
Determine what device is having problems communicating with iCloud by editing a contact on one of the devices and then checking if it updated on
http://www.icloud.com
Once you've determined which device is not working properly, on that device, go into airplane mode and then switch the contacts toggle to off. Then restart the device, disable airplane mode and then switch contacts back on.
Worked for me.