For the record, it's even possible to have tiles look like they have more colors by overlapping sprites but that's not practical because of the 8 sprite per scanline limit, and the 64 sprite limit. Also of note is that you can write different colors to the first entry of of the palettes which use the universal color from the first palette, but it doesn't affect how anything is displayed. The PPU doesn't even read them.
Question from the dimwit - what are scanlines and what purpose do they serve regarding palette/sprite limits?
A scanline (for this purpose) is a row of pixels across the screen. (ptoing beat me to it, but I'll go more in depth) NES' PPU (picture processing unit) will only render 64 "sprite pixels" in any one row. (A transparent pixel of a sprite still counts.) Since each hardware sprite is 8 pixels across, you can have 8 sprites in a row (In other words, they Y values are all the same), but if you add a ninth sprite with the same y value, it will not be drawn to the screen at all. If you moved the ninth sprite 4 pixels down below where the others are, however, the bottom four pixels of that sprite will be drawn. (since the bottom of the ninth sprite is below the eight scanlines that the first eight sprites are occupying. It's an important distinction. It's divided into rows of 256 x 1, not rows of 256 x 8 [For NES]) This is where "sprite flickering" comes into play. You may have noticed in NES games with lots of sprites on screen at once, parts of enemies or whole enemies will start to disappear and reappear. This is flickering and contrary to popular belief this is not done automatically. They do this because having enemies "flicker" is certainly a better option than having the possibility of them not appearing at ALL! (since an enemy not rendered to the screen could still hurt you.)
Edit: And to more fully answer your question, the scanline limit doesn't directly affect your use of sprites, nor your palettes. It only makes the possibility that some sprites won't appear on screen. The issue is that if (like Megaman or my 12 color example) you use multiple overlapping sprites to get more colors, you cannot have as many enemies standing on the same horizontal plane as your character without immense flicker.
For instance, say your character is 16 x 16 pixels and you use all 12 colors on him for an extreme example. That means you're
A: already using ALL eight sprites in every scanline the hero occupies and
B: Using 16 of your 64 sprites JUST for the hero character. The other issue is that the palettes you chose for the hero better be reusable for the enemies, since they have to be reused for them. All the spaces are gone.
Any other questions, please PM me. I didn't intend to start this discussion in this guy's topic, only clarify.