As the other guy said, you need to make sure Apple ID email addresses are exactly the same on all devices. For example, if your main Apple ID email address is @gmail.com but you also have an @icloud.com address through Apple, just make sure all devices are signed in to iCloud with the same address.
I have separate accounts for the iTunes store side and another iCloud account with no payment method attached and is running iCloud on all my devices. This is the account I use for FaceTime, iMessage, mail, contacts, etc...As far as all those services go, they are using the same email address. Surely someone has to have a similar configuration to this one.