I thought about this sometime ago but computers were too slow to pull off something like that. My idea was building a custom NES emulator with a super charged PPU that could support more than 4 color per tile (8,32 or 256 color for example). The emu would support "graphic-packs" custom-fited for popular and simpler games. The graphic packs would contain the following data: the location in the NES rom of all original 8x8 4 color tiles, the replacement hand designed 8x8 256 color tiles, the original palette data pointers (or included data to match dynamic palettes) and the replacement 256 color palettes. Those would have to be carefully designed to have 4 permutable groups of colors, and the tiles designed accordingly using the color on the same "group" as the original pixel. The way it could work is that by intercepting any writes to the name table, matching and displaying the appropriate tile, and by monitoring the current background and sprite 4 color palettes every frame, matching the corresponding 256 color palette in the graphic pack.

Is this thing possible? Is there a need for it? Will someone "waste" precious time doing something like this?

On related note, I've converted most of Metroid 1 to isometric 3d using the original graphic sculpted in a 3d voxel matrix, smoothed by Marching Cubes (that sure makes a lot of buzzwords hehehe). It currently runs online using the Shockwave plug-in, I've written my own "platform game" code that tries to mimic Metroid and I'm currently working on enemy AI. But I would sure like to have a custom fited Emu that could play Metroid using my demo's 3d graphics. That shouldnt be so hard with an even more adapted solution. It's easy to find as pointers in RAM the x and y pos of Samus and other sprites on the screen and her location in the main map. Kinda like that 3d Pac-Man thing. (What a great way to finish this post since I don't know what to write anymore)

Anyway if you want to try out or see screenshots of my online 3d Metroid conversion, go at:
http://pages.infinit.net/voxel/home.htm

Voxel