Tomazine,
Eu não entendo quase nada do Ubuntu, mas ele só pode estar lendo essa informação do modem ou do roteador, caso utiliza um, portanto, sugiro quando receber essa mensagem, desligar o modem (e o roteador, se houver um) durante um minuto, ligar novamente e tentar conectar outra vez.
Caso esse procedimento não solucione o problema, se tem apenas esse computador utilizando o Velox, ao sair do Windows, desfaça a conexão pois assim ela não estará sendo usada quando iniciar o computador pelo Ubuntu.
Boa sorte!
Abs,
AC