Simple suggestion, really; When going from one Dmap to another, the palette fades from the old to the new palette. Good examples are passing through Overworld Dmaps, going from a room without lava to a room with it(and it brightens up), or fading from a memory from the past to the current time.
Warp Effect: Color Change
If it was easy to implement, I suspect it would have been implemented already. But, you never know.
You just have to take the differences in the colors by RGB values and divide it by the # of frames to the final colors. It can't be that hard. Or you could just change by one per frame until the final value is reached.