Prueba a descargarte el scrip/bin
sakis3g.
http://www.sakis3g.org/con este pequeño archivo ejecutable puedes conectarte a internet via modem USB sin necesidad de ninguna herramienta del sistema.
Funciona en modo consola y gtk. Suele detectar los parámetros de conexión (APN) y si no lo hace te los pide.
A mi me ha ido muy bien cuando el gestor de conexiones del sistema se pone
burro y no desea reconocer mi modem USB. Si quiero ahorrarme el reiniciar uso directamente el sakis3g y con el conecto
si o si.
Una vez que tengas este acceso a la red aprovecha para hacer la instalación de los paquetes que necesitas y ya tendrás resuelto el problema principal.