I had this exact problem as well. This is what I had to do.
Turn off / disable iCloud entirely.
Restart your phone.
Turn on iCloud.
It should now allow you to setup your info. You might also need to add your other email accounts as well. I had to.
Same issue on my iPad. I went throught the on/off/on...remove/add...restart...etc.
Then it finally added itself. I don't think there is a specific combination that works, infact I don't think I had a restart in there when it was finally added.
As suggested above, I turned iCloud off, restarted the phone and then finally to adding once again only to find that iPhone says my password is wrong in the mail app.. Really apple really needs to do a lot of work here...
Again, flipped on/off switch of mail..and then finally resolved it..
As mentioned above, there is not particular combination..It just "works" if it wants to.. lol..