FYI, I figured out a solution...
Not suitable for everyone, but faster than contacting support (which requires apple care, at least in my country) as it seems to have been the only solution for a few people...
Problem: trying to setup imessage and Facetime on an iPad 4, for my mother, who used to have an old iPad 1 (which doesn't support Facetime):
1) changed the email address associated with her account to an unused email of mine, and then verifying it.
2) Created a new account with the "old" email address, verifying it again.
3) Login in iPad, imessage and Facetime fully working
Obviously, this was an option as the original account didn't have any purchases that were necessary to keep...
Ridiculous, but all working now.
Just to be clear:
I was also getting the wheel spinning when trying to login to imessage and Facetime. No errors would be displayed.
Used every recommendation that is mentioned in the forums: date/time set automatically, reset networks setting, reset whole iPad, 8.8.8.8 DNS...
My mum's account was verified, and worked perfectly in iCloud, app store, etc...
To further prove that the problem was with the account and not the device:
- Using my account in the iPad that gave her trouble, worked perfectly
- Using my mums account in my iPad would not
Hope this helps some people! Good luck!