Eu me deparei com um problema que me lembra o que você está experimentando. No meu caso, desligar o wireless com o switch de hardware desligou um switch de software. Tente digitar o seguinte comando em um terminal: $ sudo rfkill desbloquear todos
Isso resolveu o problema para mim (com o Ubuntu 11.04).