First, the downloading of maps that you do not have is normal. I get that all the time.
Now to your problem:
Try using the Nexuiz straight from the Alien Trap website. You can download it from here:
It is a pretty big download, about 800+MB. Download it to your /home directory.
Then right-click on the zip file you downloaded and choose "extract", or whatever it says. Or open a terminal and run:
Then open a terminal and cd (change directory) to the nexuiz directory that was created when you unzipped the nexuiz file that you downloaded:
Or it may be named nexuiz with a lower-case n:
To start the game from the terminal, you will need to use one of the 64bit launchers since you are using 64bit Ubuntu. So just run:
This should launch the game and get you into any multiplayer game. This is how I have always run Nexuiz. This way you can get the newest versions of nexuiz when they are released from the Alien Trap site without having to wait for the Ubuntu devs to add it to the Ubuntu repos.
Rationale for this:
I have just noticed that if I try to launch nexuiz by running:
then I get the same error message. The nexuiz-linux-sdl.sh is a generic launcher that is supposed to run the game whether you are using 32bit or 64bit linux. But if I use the specific ./nexuiz-linux-686-sdl for 32bit linux or the ./nexuiz-linux-x86_64-sdl for 64bit linux, then I don't get this problem. The nexuiz that you installed from the Ubuntu repos may be tring to run the generic nexuiz-linux-sdl.sh launcher. So you then get that error message.
Note: Running Nexuiz this way will not conflict with the nexuiz you have installed from the Ubuntu repos.
Hope this helps. Write back with your results.
BTW, We both have the same nvidia graphics cards. The 8600GT will run nexuiz just fine!
BTW #2, Your profile says you are running 7.10 Gutsy. Please update your profile so everyone knows what version of K/X/Ubuntu you are running.