VNC actually doesn't have a 256 color option as you'd think of it. It definitely supports more colors, and the low-color version has a static colormap (BGR233, IIRC). Progue around in your VNC client and you should find an option to select different color depths.