I recently upgraded my Mum's pc from Windows 8 to 8.1, prior to the upgrade she was logging in with a local account. Now that I've upgraded her to 8.1 we're trying to link to her microsoft account. I managed to create a linked account for her on my PC, and she can log in to outlook.com, so I don't think it's an issue with the account.
What happens is we click on the "Link to Microsoft Account" and are then prompted for her local password, we enter that and wait. After a while we get a message "This service isn't available right now- Please try again later."
The next step I can think of is to reset windows, but I'd rather not.