I LOVE that game. And there's a great version availble for Ubuntu. I think I found it under the Applications->Games->"look for games" menu item.
The only problem with xconq is that clocks run faster in the presence of a computer running that software. When I'm playing that game, it seems that "a few minutes of playing time" makes my clocks jump forward a few hours!