Most likely your video drivers...
Double check that antialiasing is off....
your loss is nearly half of what you had.. sounds like antialiasing for shure..
reduce resolution to 640x480 and work your way up... Make shure your color is at 16bit not 24 and 32 bit. (fill rate)
AK Desert aka the pizza map the textures require more resources...
2 cents
DoctorYO