http://packages.ubuntu.com/feisty/games/nexuiz
You are correct - there is a broken dependency in the package. It looks as though they intend to push out 2.2.3 (at least) for feisty, which is pretty good news. However they only sync'd the nexuiz and nexuiz-server packages (and not the other two!) with Debian. According to the bug reports Adrien Cunin is in the process of fixing that, as of yesterday, so the package should be upgradeable soon.
If you subscribe to the bug, you can receive email updates:
https://launchpad.net/ubuntu/+source/nexuiz/+bug/84283