Terminal server resolution

I have clients using MS Terminal server to log into and access applications. The problem is that that they can only get 256 colors.
THe server show True Colors. Does anyone know how to resolve this or where to go for support.
Thanks in Advance.