Unfortunately this is not possible with Windows 2000. 256 Colors is the maximum resolution for terminal services sessions for this OS. This isn't a limitation of the server OS, but of the protocol. Unfortunately, you can't upgrade the protocol on the server side, so to get greater color depth you'll need to either upgrade to Windows Server 2003, which does have a version of the RDP server component that supports full color, or install MetaFrame on the Win2K terminal server and get greater color depth using the ICA protocol.
This was first published in April 2006