An 8 bit display meant that you basically had a lookup table of size 256, and each entry mapped to an 18 bit colour (6 bits each for R, G & B IIRC). These days it's kinda normal for a bit geek to have numbers like 1024, 1048576, 16777216 and 4294967296 permanently burned into your brain. Back then we also had 262144 burned in -- the number of colours we had access to.
The best part about palette cycling was that you didn't have to wait for the VBLANK to make your changes. For most frame changes, you'd have to wait until the cathode ray hit the bottom of the monitor and was slowly making its way back up to the top to scan through again. You had to make all writes to video memory at this time to avoid screen fuzz, ie, half a screen with the old frame and half with the new frame. Palette cycling could happen at pretty much any time, so you'd just hook it up to the timer interrupt and let it go.
http://www.gamedev.net/reference/articles/article373.asp
which also tells you why Michael Abrash is God
And it's a very slow process, hard to automate. So as games got bigger, it was hard to have that many individual paintings. You're basically doing an animated movie when you've got 2D pixel graphics.
That's why mainstream games can't make too much money with that, and why on the other hand, pixel-based games have seen renewed popularity with the advent of downloadable indy games for major console platforms.
Much of the "pixel art" made even at ~320x200x256 is sourced from oil paintings, cels, 3d, or photography and cleaned up with pixel editing. Cleanups can work wonders for any source material at that resolution, but if you look at games from the later 90s which applied these methods to 640x480 and above, the art taken from other sources tends to look like a paper cut-out once composited, because the alpha is colorkeyed, not per-pixel, and no amount of cleanup could hide that. Now that we can use per-pixel alpha everywhere and apply shader effects, 2D is a lot more flexible than it used to be.
EDIT: Actually, Braid.