I ran into the same problem with game.so. I installed the game from the debs that are provided by the ufoai sf site (
http://sourceforge.net/projects/ufoai/files/UFO_AI%202.x/2.3.1/), so no third party packaging, I guess this is the "official" release. game.so went under /usr/lib/games/ufoai/base/game.so, where it is not looked for by the game.
I saw some comments here with the feeling of "this is a packaging issue of the distributor, buzz off, it's not our fault, solve it with whoever you got it from". Well, OK, I came here to the forums to look for a solution, but probably many people wont do that and give up with "ehh, another crappy software, remove", and will miss this otherwise suberb game. Just because of a silly misconfig. So I suggest you take some care of the packaging of your product, at least in the distributions that you advertise on your download page... That is unless you write this game for your own entertainment and don't care at all how it spreads around the world
Nevertheless, great game, great work, keep up!