This typically happens when the terminal session uses a 15 bit display color depth.
You may have requested a higher color depth in the Remote Desktop client, but the default group policy on XP/2003 limits the maximum display color depth to 15 bits.
To solve this, you can either try connecting with a lower color depth (256 colors), or set the group policy on the server computer to allow a higher color depths, and then connect requesting 16 bit color depth.
To set the group policy for this, please see MS KB article 278502.