Terminal Server can do more than 256 colours, at least in terms of internal architecture - Citrix MetaFrame is based on TS and supports up to 24-bit colour.

I don't think that RDP supports more than 8-bit, though - you may need Citrix software to get more. Greater colour depth alone is unlikely to be a sufficient reason to invest in MetaFrame, though!

Disclaimer - I work for Citrix.