Ok, I now have it working. The 6.1 client did not work for me. The 7.0 client does which can be downloaded here: http://support.microsoft.com/kb/969084/en-us
In addition to this I had to enable two rules in my Inbound firewall:
1) Remote Administration (RPC)
2) Remote Desktop (TCP-In)
Hopefully this will help others. Thanks for all your help.
Edit 1: also, if you want to keep Network Level Authentication for RDP sessions on your 2008 server and you're connecting from your XP SP2/3 workstation than there are some registry changes which you will need to make in order to enable CredSSP. This is from the page: http://support.microsoft.com/kb/951608/
- Click Start, click Run, type regedit, and then press ENTER.
- In the navigation pane, locate and then click the following registry subkey:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Lsa
- In the details pane, right-click Security Packages, and then click Modify.
- In the Value data box, type tspkg. Leave any data that is specific to other SSPs, and then click OK.
- In the navigation pane, locate and then click the following registry subkey:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders
- In the details pane, right-click SecurityProviders, and then click Modify.
- In the Value data box, type credssp.dll. Leave any data that is specific to other SSPs, and then click OK.
- Exit Registry Editor.
- Restart the computer.
Windows server 2008 provides a Routing and Remote access service, this can allow you to use NAT.
An explanation of NAT is provided Here
Below are taken from technet
Install RRAS
Applies To: Windows Server 2008 R2
You install RRAS by using the Add
Roles wizard in Server Manager.
Membership in the local Administrators
group, or equivalent, is the minimum
required to complete this procedure.
To install RRAS Perform one of the
following two steps to start the Add
Roles Wizard:
Start Server Manager. In the main
window, under Roles Summary, click Add
roles.
In the Initial Configuration Tasks
window that appears when you first log
on, under Customize This Server, click
Add roles.
On the Before You Begin page, click
Next.
Note This page does not appear if you
previously selected Skip this page by
default. On the Select Server Roles
page, select Network Policy and Access
Services, and then click Next twice.
On the Select Role Services page,
select Routing and Remote Access
Services.
On the Confirm Installation Selections
page, click Install.
On the Installation Results page,
review the status, and then click
Close.
Open the RRAS MMC Snap-in
Applies To: Windows Server 2008 R2
Use these procedures to open the
Routing and Remote Access MMC snap-in.
Membership in the local Administrators
group, or equivalent, is the minimum
required to complete this procedure.
To open the RRAS MMC snap-in by using
Server Manager To start Server
Manager, click Start, click
Administrative Tools, and then click
Server Manager.
Expand Roles, expand Network Policy
and Access Services, and then click
Routing and Remote Access.
Enable and Configure NAT
Applies To: Windows Server 2008 R2
Network address translation (NAT)
allows you to share a connection to
the public Internet through a single
interface with a single public IP
address. The computers on the private
network use private, non-routable
addresses. NAT maps the private
addresses to the public address.
Membership in the local Administrators
group, or equivalent, is the minimum
required to complete this procedure.
To enable network address translation
addressing In the RRAS MMC snap-in,
expand Your Server Name. If you are
using Server Manager, expand Routing
and Remote Access.
Expand IPv4, right-click NAT, and then
click Properties.
If you do not have a DHCP server on
the private network, then you can use
the RRAS server to respond to DHCP
address requests. To do this, on the
Address Assignment tab, select the
Automatically assign IP addresses by
using the DHCP allocator check box.
To allocate addresses to clients on
the private network by acting as a
DHCP server, in IP address and Mask,
configure a subnet address from which
the addresses are assigned. For
example, if you enter 192.168.0.0 and
a subnet mask of 255.255.255.0, then
the RRAS server responds to DHCP
requests with address assignments from
192.168.0.1 through 192.168.0.254.
(Optional) To exclude addresses in the
configured network range from being
assigned to DHCP clients on the
private network, click Exclude, click
Add, and then configure the addresses.
To add the public interface to the NAT
configuration, right-click NAT, and
then click New Interface. Select the
interface connected to the public
network, and then click OK.
On the NAT tab, click Public interface
connected to the Internet and Enable
NAT on this interface, and then click
OK.
If you want to add additional public
addresses assigned to this interface
or configure service and port mappings
to computers on the private network,
see IPv4 - NAT - Interface -
Properties Page.
To add the private interface to the
NAT configuration, right-click NAT,
and then click New Interface. Select
the interface connected to the private
network, and then click OK.
On the NAT tab, click Private
interface connected to private
network, and then click OK.
Best Answer
Figured it out, it has to do with the VPN connection, to fix use this suggestion from .NET Answers:
Apparently the issue is that VPN connections do all traffic over VPN, including incoming. Not sure why it explicitly was ignoring incoming traffic that Wireshark showed, but this works.