Just noticed this now, but basically AI War is not a true fullscreen application, and because of it's inclusion of GDI+, it cannot be. So when you change the "resolution" of the game, you're just changing the window size.
I do have good news, though: this is one of the many benefits of our upcoming switch to Unity 3D, that it will then be able to run in true fullscreen mode as well as windowed mode, and thus your resolution changes would work as expected.