Thanks very much guys, here's the new version:

Changed the palette slightly (I'm pretty happy with the saturation btw, and the thread suggests this is highly subjective here anyway

)
Added a tile, moved some pixels, changed the small character. He did look like a girl, the head wasn't separated from the body at the back of the neck and thus it looked like he had plaited hair or something.
I just realized that in theory I have 256 tiles, more than enough to completely eliminate the grid. I'll probably rework this as soon as I have other backgrounds that use the same tileset.
GBC restrictions btw.: 8 4col background palettes, 8 3col+transparency sprite palettes. The colors have a bit depth of only 5 but there aren't any other restrictions.
Edit:
Btw, here's how this is going to actually look in-game:

The overlay isn't complete yet, I still need to do the logo and refine it a bit.