УРАА!!! Получилось... Целый день промучался с Wi-fi... Перепробовал все алгоритмы шифрования, прошил роутер серой прошивкой и натанцевался с бубной по самое не хочу... Не знаю, возможно многие из совершенных мною действий косвенно повлияли на результат, но действительно исправило ситуацию следующие:
Я скачал с офф сайта адаптера официальные драйвера (они там только для Win), распотрошил их и установил на Ubuntu и вооля, все сразу заработало. Получаеться, что проблема была в устаревших драйверах на адаптер.