This problem was overcome with the new TS Client called RDC(Remote Desktop Connection) which is shipped with XP and 2K3. You can download this TS client from MS website and then from the Display tab -> Select Colours (256, 15 bit, 16 bit and 24 bit) for that connection.