Just seen this thread and wanted to chime in because I've been having some issues with it myself.
Twice in the last 24 hours and about six times over the last couple of weeks, my iPhone has thrown up an alert box asking me to enter my iCloud password in settings because it couldn't verify (or something like that).
Whether entering it, or cancelling the prompt, I then receive two emails saying my iPhone automatically been removed as a trusted device.
I log in to my Apple ID and re-enable it and it's ok again for a while.
There aren't any other devices on my account besides my own (and one other) so I've not been hacked or anything.
Any ideas?