Siga os passos que a Cipsoft postou no forum deles, está explicado em português por um usuário aqui do fórum:

http://forums.tibiabr.com/threads/49...20#post6831420

Aparentemente as conexões que começam com 189.X.X.X não estão conseguindo entrar no jogo, então se você ficar reiniciando seu modem até ele pegar outra faixa de IP, por exemplo 179.X.X.X, ele funcionará, mas há pessoas que relataram que nem assim conseguem logar.

Realmente é um problema da Velox no Brasil, mas no Tibia.com há inúmeros Mexicanos com um provedor deles lá com o mesmo problema, o melhor a fazer é o tracert do link acima e esperar que eles resolvam o problema.