If notch puts in a evaporation, he could add flooding.
A tornado.... hmmm... (pictures a blocky tornado)
Ice storms, yes. If more depths are added to snow, or just a gust of wind pulling you and everything else in one direction would be cool.
I'd like to see rain. Add proper in game rain, so it hides enemy footsteps and it forces fog to be at near or tiny range (depending how bad the rain is.)
I'd like skeletons and zombies that are on fire to set fire to trees as well. With natural reforestation (saplings plant themselves if left on the ground), this could work and would be a natural process of changing the landscape.