I'm working with VGA DSUB-15 output, however VGAX only allows for 4 colors. I'm using an Arduino Nano that uses an 8-bit atmel chip, and I've seen many 8-bit computers of which have a bit more than 4 colors.
Are you using the Arduino to directly drive the VGA, or are you using a shield. If you're directly driving the display, I think the limitation is on the Arduino because with only 2kb or RAM, you can't really store all the pixel data. And the duino is also generating the high frequency vsync and hsync signals.
The VGA interface uses full analog signals for Red, Green an Blue video. There is no limit to the color levels in the VGA standard.
However, it is not unusual to find that minimalist implementations of VGA in microcontroller products use Digital to Analog Converter (DAC) techniques with a limited number of bits of resolution. For example, using two bits of resolution for Red and Blue, and three bits of resolution for Green so that the pixel information will fit into an 8-bit byte, etc.