Olá, desculpe o atraso.
Eu sei que é uma dica meio óbvia, mas você não está tentando rodar o mesmo Tibia que você usa no Windows né? As distribuições Linux não rodam os programas . exe nativos do Windows, você tem que baixar a versão própia para o Linux (Download).

Se não for o caso tente rodar o jogo pelo Terminal. Persistindo o problema tente rodar outros programas parecidos e veja se ocorre a mesma coisa, caso os outros programas também não funcionem, procure ajuda em algum forúm especifico de Linux.
Em ultima instancia tente reinstalar o sistema, usar outra versão do Ubunto ou até mesmo outras distribuições, a minha recomendação seria o Kurumin