If I had to venture a guess, your native resolution and the full screen capabilities of your card/driver are not in agreement, at least as far as the game goes. If you want "real" full screen, you might want to play in windowed mode and just manually set the screen dimensions in the config file.
