In Quake 3's Setup/system/graphics screen.. Do you have Fullscreen set to ON?? (This is the only area that I can find in Q3A that relates to full screen.) If for some reason, Q3A resorted to software mode during the install/first_run, it may have defaulted to windowed mode. This is the only thing that I can suggest.
I have it running in full screen in all resolutions with the 4191 driver.