To follow up from yesterday, I tried installing Windows Server 2003 SP1 on a couple more of my servers, including the host server for my virtual servers. I was able to get in through Remote Desktop afterward. I think (hope) yesterday's experience was just a fluke.
What is confusing is when you check what ports are allowed and not allowed, I notice an Exceptions tab for the overall Network Firewall, and this has Remote Desktop unchecked. Looking at Advanced/Settings and selecting my NIC, I see Remote Desktop checked (as this was the original setting). I went ahead and checked the first Remote Desktop setting, but it didn't seem to matter if this was checked or not checked as long as the default settings had Remote Desktop checked. I will have to investigate further what effect the first Exceptions tab has in allowing or preventing what the default settings are for each NIC.