I followed this guide: http://www.pokecommunity.com/showthread.php?t=283345
And I either get ugly blue and yellow lines in the background or a discolored mess, even though I did the thing with the palettes. I made my tile map with NTME, then Hurricane...they seem to be giving me the same result. The blue and yellow lines showed up when I took the clouds out, and the discolored mess showed up when I left them there. If it helps, the palette editor wasn't accepting my palette, so I had to follow the directions further down the page that involved screenshotting and putting the values in manually.
I'm using windows 7 64 bit.