I was able to restore my connectivity to the home server with the step described here. I was then able to connect to all the file shares and perform backups. However, I was still not able to connect to WHS via the Console:
Additional tools exist for troubleshooting these problems. Go download the Windows Home Server Toolkit and install it. Then launch ConnectorTroubleshooter.exe at C:\Program Files\Windows Home Server\Toolkit\
It will give you a nice (ugly) report of issues it detects, with links to MS help documentation:
In my case, when I setup my new router, I did not configure the local domain name on my LAN properly. I learned this lesson a long time ago, but forgot about it. Without a domain name on my router's LAN, DNS requests will be fulfilled by my ISP. Obviously, name resolution performed by my ISP is not going to work for resolving machines on my local LAN. The first link on this problem report reminded me of this:
IP address mismatch
UPnP protocols and name resolution produced different IP addresses for your server.
If your broadband router is configured to use a dynamic DNS (DDNS) service, you may experience name resolution problems with Windows Home Server. To work around this problem, disable DDNS on your router while you install the Windows Home Server Connector software. After you finish installing the Connector, you can enable DDNS again
This may also happen if you use DNS for name resolution on your network and your name query request was resolved by your Internet service provider's (ISP's) DNS server. Your ISP may have a computer with the same name as your home server. If you use a local DNS server for name resolution on your home network, ensure that you have a local domain for your home network and that there is an appropriate address record for your home server. Your home computers should be configured to use this DNS server for name resolution.
http://download.microsoft.com/download/2/7/2/272d0c12-bed8-41bc-a2a5-f55682a63f34/95508.htm
Providing a local domain name on my new router brought my WHS Connector back to life. What's strange about this is I was able to successfully connect to my WHS file shares (by name!), but the Connector wouldn't connect. Odd... In the past when I didn't have this configured correctly, I had no connectivity at all (as logic would suggest)
On the D-Link A3, here's where you do that:
