Hi,
I just solved this problem, so I wanted to share my experience.
I was having the following error on compiling FS2_Open 3.6.9 from CVS:
ERROR: "A minimum texture size of "1024x1024" is required for FS2_Open but only "512x512" was found. Can not continue." at graphics/gropengltexture.cpp:543
I am using Ubuntu 7.4 Feisty Fawn, with X.org 7.2
Initially, I thought the problem must be due to AIGLX being enabled in Feisty by default, but after searching through a myriad of forums, I found a reference to a program called driconf, obtainable at
http://dri.freedesktop.org/wiki/DriConf, or through your friendly neighborhood apt source. Download the program, and run it. It is written in python, so you shouldn't have to compile anything. After running it, go to Image Quality tab. Scroll most of the way down, and change the "Support Larger Textures not Guaranteed to Fit into Graphics Memory" option to "Announce Hardware Limits". Go figure.
Restart X. Run FS2_Open. It should work.
I am not sure if this option is dangerous (could enable textures too big for your card to handle, overfilling your memory and making your computer explode ;-) ) So use at your own risk.
Hope this helps. I know I spent a long time pounding my head against this, and came to the solution quite by accident, so some other n00bs like me are certain to appreciate it.