Just a new colour set for the background tiles. Thanks for the tip, EyeCraft: it really rocks. Now I'm set up to follow the other pieces of advice you pointed out.
Sorry to dig such an old thread to tell that, but I thought that'd only be justice to do so ...
Btw, these might not be the bestest colors possible, but remember: the NDS only allows RGB values that ends up with F or 7 (5bits/color channel)
I had
a few missed attempts while trying to blindly copy colours ... what made it work was to build up a mockup first (the small image nearby) with BG, FG and character tiles alltogether in such a way that contrast issues became obvious. Once in that setup, with a 32x32 area to focus on where all the important things were there, I could bring the BG colours down, almost to grey, although keeping the blues with a higher value (blues and purple = dark, cold shadows. That's how our bluesky world and cone-rod eyes work ^_^)
Hope it'll help others as well.