RDP fakeout when connectiong: does nothing, no error
Solution 1:
I've encountered this type of behavior several times so far with Windows 8/8.1 or Server 2012 machines when they've been rebooted and have a lot of updates to install. For whatever reason it appears that the RDP password prompt will appear if you try to connect while it is still installing updates even though you can't actually connect. In those cases it has resolved once the updates have finished installing, but depending on the number and type of updates it can take quite a while because sometimes it will reboot several times during the install process.
Could be completely unrelated to your problem especially since your question was asked before Windows 8 was RTM, but I thought I'd add this reference for additional info. It's happened enough times to me in completely different environments that I don't see it just being a random quirk.
Solution 2:
IT has been my experience that when you can authenticate but it does not launch the desktop, the remote server is installing updates or is in the middle of building the desktop environment. give it a few more minutes and try again. I have seen it take as much as 10 - 15 minutes (after installing updates it may reboot again) to be viable again.
Solution 3:
The credientials are stored as the connection is being built. So even though it asks, doesn't mean it is connected when doing so. Verify that RDP is running on that machine and that the Firewall isn't interfering with your connection. Also, check the event logs to see if possibly the service crashed for some reason. My first vote would be the connection is being blocked by the windows firewall.