Earlier this week there was an obligatory Xbox 360 update that we had to install or we could not login to Xbox live.
After installing this update, none of my kids could login to Xbox live as it forced us to go through a security check, wanting me to confirm their email address and then add a mobile number, and it then refused the number telling me I had added it already and said they had to login at account.live.com/p which then required the parent (me) to login and approve them.
(nb: So Microsoft put you in a catch22 it seems, don't upgrade and you can't login, do upgrade, and you still can't login.)
It was at this point after *I* login I got the message "Your account is missing a full name or birthdate. Visit account.live.com to update the required information, and try again."
This was of course nonsense as my account did have those details so there was nothing I could do. Googling the issue I found loads of others with the same problem on the forums, and Xbox live chat had massive queues, so it would seem they had broken things for a lot of people.
So I thought I would share the solution for anyone else stuck in this endless loop.
I was given numerous suggestions by Xbox support, all of which failed, but finally the solution was reset the password on each account and they were then able to login again. There was a delay of 10 minutes or so on one of them, but eventually they were all able to login.
Presumably you can just login to each account and reset the password, but I used THIS LINK to do it.
If this doesn't work for you, then I suggest contacting Xbox live support for help.