Eh, Spiritcrusher, you missed the point there. The first category was things that were marginal upgrades, while the second category was things that actually involved deleting.
As it is, Fawfulfan, I am entirely for you removing AAZ as it is, and building a new, better one from the ground up. I'd be willing to help you with the design of it, too. The way it stands, AAZ is right now just Mars. With acid. And castles. The thing is, Mars + Acid + Castles isn't a very nice combination. Combining an ugly red dusty planet with UFO's and medieval technology is frankly, pretty silly. It's not very imaginative, beautiful, inspiring, or anything at all. It's just... Yucky.
That being said, you're gonna need a plan for the new AAZ, if you choose to make one.
I think what you need to do is entirely rework the way these aliens work, being disconnected from Earth through they're entire existence. Basically, build a new culture for these aliens. I have quite a few ideas here that I want to share with you, regarding that new culture.
#1: What are these aliens like? Are they big hulking brutes? Are they relatively cute creatures, like the Wisps? Are they green martians, like you have in the current AAZ? What they're like will determine the entire demeanor, and even stature, of everything on the planet.
#2: How different are the standards of architecture and beauty, from what we humans have invented here on earth? What do the buildings look like? Considering this would be very important, because it would help you give an alien look to the buildings of the world, something very important for a society that had years and years to come up with completely different things than humanity has. You could do everything from angular, jutting buildings, to smooth, crystalline structures, to underground towns and cities. (Expanding on that last random idea: Perhaps the solar rays from the planet's star are too powerful for anything to survive on the surface, so the aliens build civilizations inside the world? Maybe there could be giant crystals embedded in the surface of the planet, which serve to filter the intense light, and give it passage into the underworld, where the aliens use it to grow the necessary food?) Of course, that's just an idea I came up with on the spot, there's plenty of other possibilities that you could come up with.
#3: How different is the ecosystem? Don't forget, on a different planet, the conditions of the world would mean for an entire different breed of plants and animals. Although animals certainly aren't much of an option in SRB2, plants certainly are. One of the things AAZ in it's current state is missing, is any form of life, plant especially. I don't care whether it's a ravaged planet or not, there should be some signs of life. Flora is pretty much a necessary part of any life, so there should at least be some evidence of it. Again, there's a lot of possibilities for what you could make the plant life like. Is it giant fungus like plants? Perhaps the plant life is somewhat more alive than it is here? Even the idea of simply changing some colors around slightly would make it seem somewhat alien. Blue trees? Purple horizons? Teal grass?
#4: How has Robotnik's havoc influenced the planet? Many ways you could show this, everything from abandoned buildings, smoking craters, scorched farm fields, and captive aliens. Use your imagination, and I'm sure you can do a lot of interesting things with it.
Perhaps Act 1 could be in a relatively unharmed part of the planet, but throughout it, you would gradually come upon more and more destruction as you followed the path of Robotnik's trail of Armageddon? Then, Act 2 could take place in his master fortress, where he controls the havoc from, and imprisons any that resist his will?
There's just a lot of unexplored imagination and possibilities when it comes to this stuff. I think you should seriously consider doing something new with AAZ.