Hi, I installed Fedora 13 x86_64 a few days ago and it works like a charm.
My first question would be: did you install real 3D support for your graphics card or are you working with the open source drivers? If you didn't, follow the instructions on
The Unofficial Fedora FAQ to install the nVidia drivers (ATI drivers are not out yet, so if you have an ATI card you'll have to wait).
If it still doesn't work after that, remove the q3config.cfg from ~/.openarena/baseoa and try to start the game again, it might be there is a wrong video mode (the r_mode cvar) in that config file.