i think i'm agreeing with nesrocks here, it makes me think of how a spruce forest goes from mid-dark cold green to all reds and oranges in the world during sundown. It's a very strong means for symbolizing evening/sunset this way, even if it in reality is just a small portion of the evening.
I actually tried a reddish background more than once. We had yellow, solid red, purplish/pinkish. But it always had the problem that it hurt my eyes. After playing level 1 and 2, the color in level 3 just didn't look very pleasant. That's why I decided for the dim blue and the gray clouds.
Here's an idea though. You could try and replace a few clouds with stars coming out. Just by a little during evening, and then some more during night. I think it could really help conveying the sense of time shifting, and require only a very few extra characters in memory. I've made it with a little as two, but that's on the conservative side.
The problem with this is: We don't have a single graphics tile left. We literally used all 256 tiles, both in the background and for the sprites.
Also, the game is basically finished. The only reason why it's not out yet is all the external stuff: Artworks, manual, box etc. I will include one more sound effect that came to my mind in the meantime, but I won't do any major stuff anymore like a dynamic background image.