Can't access an XP remote desktop!

So...I'm trying to connect my MacBook (3.1) to an XP remote desktop (via the MS Remote Desktop Connection for Mac client, version 2.0.0) at my workplace. I used to be able to do it, but they vamped the network a little. I contacted our tech support people, and they have confirmed that they changed the IP address and told me what to put in.

But...it's just not working. I have to connect to our VPN first -- which works fine -- then do the Remote Desktop connection...but RDC just hangs for several minutes.

Now, I know it's not a hardware issue, because if my boot my MacBook into Ubuntu, I can connect with no problems in Ubuntu.

Any thoughts as to what I should be looking for? I have confirmed I'm putting in the correct IP address, and again, the VPN connects fine (I'm able to access our network drives)...