Well, it's not just about how many colours you put on screen that mattered, it's how they were used too. After all, Syndicate only used 16 colours for the in-mission graphics (even the PC version which used 640x400 for the in-mission graphics, no more than 16 colours were used).
