Apparently the RDC Client 6.1 that comes with SP3 for Windows XP does not support Network Level Authentication (NLA) by default. A couple registry values need to be changed to enable support for NLA. Heres the article I found that explains the change: