Most people don't realize how limited the palette actually is on NES. The entire gamut is only 54 colors (nominally 64, but there are duplicates and an "unsafe" entry), and any 16x16 block can only have 4 colors. There are some ways to work around this with clever hacks, but it was mostly the artists being clever rather than the programmers.
