Unfortunately I don't think there's enough information here for us to provide a fix or workaround. It may be a problem with the AI code or something that comes after it.
Check on the FreeOnion website for any issues, fixes, and an updated version (if any). Check the forums, and any other resource they have available. If anyone knows, it'll be the creators and code maintainers that can help solve it, better than a general linux gaming forum (no offense guys).
Does FreeOnion have a --help or --verbose function?
Ubuntu is horrible at some apps when it comes to latest and greatest. Transmission is one of them I know of off the top of my head (Ubuntu runs 1.06 when it's now up to 1.34).
Unfortunately I'm not aware of FreeOnion at the moment. My laptop may have better luck, but unfortunately it's an older ATI card and I haven't gotten around to accelerating it, if it even can be (ATi IGP 320M 64MB shared).
What specific video card are you using? Perhaps it may not be capable of running FO. My lappy certainly isn't capable of running WoW and crashed all the time in Windows.