Hola, ese problema por lo general es debido al Gnome Network Manager, si no quieres complicarte la vida hermano, podes utilizar wicd y luego solamente o agregas a Aplicaciones al Inicio, y la cosa se soluciona.
Instalacion: La misma de siempre xD aptitude install wicd
Instalacion: La misma de siempre xD aptitude install wicd