Inicialmente instalei o Wine 0.9.34. Usei o apt-get, daí simplesmente instalei o AOE o TC a partir do CD, mas como nada é perfeito, quando eu rodava o jogo aparecia uma mensagem dizendo que não foi possível iniciar o sistema gráfico.

Levei uma surra do programa até descobrir no site do projeto que existe um bug no arquivo Wine3d_interface.h e infelizmente este bug afeta todas as versões após o Wine 0.9.31. Para resolver o bug temos que recompilar esta biblioteca removendo a seguinte linha:

Instalei todos os módulos necessários para recompilar o Wine e rodei os seguintes comandos:

$ ./configure
$ make depend && make

Após recompilar o wine copiei a biblioteca Wine3D.dll.so para o diretório onde o wine estava instalado e pronto, tudo ficou normal.

Para quem não quer quebrar a cabeça, basta instalar o Wine 0.9.31 que jogo rola numa boa!