I have the same problem on a brand new machine. I noticed that the Remote Desktop Service (and others weren't running as they are on another 8.1 machine. I tried manually starting it and the process terminated. Not sure how
to proceed.
I tried running through the various fixes to get RDS and the other services it needs up and running, and only got into more trouble. I eventually fixed it by doing a repair install, so I still can't say what was wrong but whatever it was, this fixed everything.
However, it's not as straightforward as it should be if you don't have the Win 8.1 installation disk (which in your case it seems you do). If you do then try a refresh or repair upgrade and it should fix your problem. But before you that do keep a copy of all
your personal stuff especially settings for email and other applications just in case
If you have a retail copy of Win 8 and upgraded to 8.1 online then you can't do a refresh, only a win 8 reinstall which solves nothing since it's the upgrade from win 8 to 8.1 that causes the problem. You HAVE to have the full Win 8.1 installation disc which
MS won't officially let you download.
Here's what I did and it worked for me.....
Go to http://windows.microsoft.com/en-us/windows-8/upgrade-product-key-only where you can get a copy of Win 8.1.
For instructions on how to download Win 8.1 go to http://www.techrepublic.com/blog/windows-and-office/get-the-iso-you-need-to-create-your-own-windows-81-dvd/
Once you've burned the Win 8.1 disc you should be able to use it to perform any maintenance you want and most definitely a refresh and other things that are impossible without it. In using it I don't recall having to use my product key at all which concerned
me slightly (but keep a record of any product key numbers that come up just in case) but after repairing Windows and checking my key in the PC it's the same as my original Win 8. In my case because I had a system image backup I didn't care that much since
I could always revert back to it but based on my experience this workaround works and there's not a lot that can go wrong I don't think.