Amigo, baixe a versão própria para linux se você tá tendo problemas com a do Windows. Basta você seguir o tutorial do site que você já postou, ou digite os seguintes comandos no terminal:
você@Seu-PC:~$ cd Downloads/
você@Seu-PC:~/Downloads$ wget http://www.netadm.com.br/util/PacketTracer601_setup_linux.gz
você@Seu-PC:~/Downloads$ tar zxvf PacketTracer601_setup_linux.gz
você@Seu-PC:~/Downloads$ cd PacketTracer601/
você@Seu-PC:~/PacketTracer601$ ./install
Depois disso basta seguir as intruções que aparecerem no Terminal e você terá o packet tracer instalado. Ou se você não quiser instalá-lo depois de descompactar o tar.gz (tar zxvf PacketTracer601_setup_linux.gz) entre na pasta do packet tracer, depois na pasta bin e depois clique duas vezes em PacketTracer6 e espere.
Ou se você quiser executá-lo do terminal digite:
você@Seu-PC:~$ packettracer
Qual Ubuntu você usa? Eu acabei de testar no 13.10 e não funcionaou, funcionou apenas no 12.04.04 LTS
EDIT: faça o seguinte se usar o 13.10:
-acesse a pasta /opt/pt/bin
- clique duas vezes em PacketTracer6
- vai solicitar a instalação do PyPar2, instale-o
- Com isso siga as instruções, simplesmente clicando em ok, go!, continuar, etc...
OS ÚLTIMOS QUATRO PASSOS DERAM ERROS, mas qualquer coisa siga apenas para se instalar o PyPar2
Faça o seguinte e veja se funcionou:
$ cd /opt/pt/bin
$ sudo chmod +x PacketTracer6
Depois tente executá-lo com:
$ packettracer
Bem, comigo funcionou.
Dá uma olhada e poste o resultado.
Usei este procedimento no Ubuntu 15.04 64bits e funcionou 100%!