Вы пробовали альтернативный сетевой менеджер, такой как Wicd?
sudo apt-get install wicd
Не обещает, что это сработает. Я был на одной лодке, когда вы год или два назад, и это было так оскорбительно. D:
Какая у вас беспроводная карта? Используйте эту команду, чтобы узнать.
gksudo lshw -C network