What happens when you try to RDP to the 2003 box? Does it just silently drop the connection or does it give an error message?
I've found one of these two methods to work in the past:
Method 1: Guaranteed and Reliable
Delete any occurrances of the Certificate, X509 Certificate and X509 Certificate ID keys at HKLM\System\CurrentControlSet\Services\TermService\Parameters and reboot the Server.
MS KB Article
Method 2: Might Work, worth a try on 2003 boxes if all else fails
Change the port that Terminal Services uses by editing the HKLM\System\CurrentControlSet\Control\Terminal Server\WinStations\RDP-Tcp\PortNumber Registry key. By default this is 3389. Changing it to something like 3388, then rebooting the server, may cause things to kick in OK again.
(Note: using this method, you will have to specify servername:3388 as the Server to connect to via mstsc in future. It may be worth a try to change it back to 3389 to see if that forces it to work again.)