I've never worked with Minecraft so I can't speak from experience there, but I've been programming games for many years and it really doesn't seem like it should be too difficult. Using an 8-bit colour scheme (which I think would fit Minecraft well) all you'd need for all 3 colour mappings is to add a single unsigned char to the chunk's structure. Then change the light texture to an array, and set the colour index before doing the multitextured render.
Like I said though, I've never even looked at MC's code so I might be full of shit.
