We're frankly somewhat hesistant to see this as a legacy issue, but from a strict definition point of view it is. If you find yourself with the same problem that we did, that is connecting to a Windows 2008 server via RDP from a Windows XP machine, then you'll be pleased to discover that Mark Empson's Blog has the answer.
To enable legacy support, make the following registry edit (all the usual warnings about making changes to the registry apply) :
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Control\Terminal Server\WinStations\RDP-TcpData Type: DWORDValue Name: UserAuthenticationValue: 1