I also think brighter colours are better. I understand the want for smoother transitions but I don't think the colours should suffer for it. The box art shows it to be a bright, colourful and cartoony game and otherwise it's going to end up looking like Gears of War which is most definitely the wrong mood for the game. Personally I would like to see you sticking as close to the Link's Awakening palette as possible
That's pretty much what everybody is saying to me, so I suppose that's the only way to go. I've been exploring several ways to avoid the artifacts and keep the colors bright, and I think I've finally found a satisfactory solution.
I've been trying to use just one set of palettes per section and I've finally managed to do it properly by giving up to some colors and making small changes per screen to the base palette set - because you know, small changes can make huge differences. For example, if you pay attention to the wall's border you'll see that the bottom is brown and the top is black:

And you may think this is a stupid change, but this is how it looks if I switch the palettes:

So from now on I'm going to stick to a base palette per section and make some tweaks here and there.
Why not crop the original cover art and use that for the border (after heavy dithering, of course)?
TLOZ:LA DX did something similar with some concept art from the manual.
I love the idea, but I think it would require an artist to redraw the background or to remove the characters in order to look good.