I've got a similar problem.  Used to work in Intrepid.

I get the problem using nm-applet (Gnome, not KDE) so it might not be an applet bug.

The device still works with wvdial, so the kernel driver is working.

Hardware: Huawei E630.
Network: Vodacom (South Africa)

It looks like pppd was never involved.

/var/log/daemon.log
-----------------------
Apr 24 14:13:38 swbr1435l NetworkManager: <info>  (ttyUSB1): ignoring due to lack of mobile broadband capabilties 
Apr 24 14:13:38 swbr1435l NetworkManager: <info>  (ttyUSB2): ignoring due to lack of mobile broadband capabilties 
Apr 24 14:13:38 swbr1435l NetworkManager: <info>  (ttyUSB0): found serial port (udev:GSM  hal:GSM) 
Apr 24 14:13:38 swbr1435l nm-system-settings:    SCPlugin-Ifupdown: device added (udi: /org/freedesktop/Hal/devices/u
sb_device_12d1_1001_noserial_if0_serial_usb_0, iface: (null)): iface not found
Apr 24 14:13:39 swbr1435l NetworkManager: <info>  (ttyUSB0): new Modem device (driver: 'option') 
Apr 24 14:13:39 swbr1435l NetworkManager: <info>  (ttyUSB0): exported as /org/freedesktop/Hal/devices/usb_device_12d1
_1001_noserial_if0_serial_usb_0 
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  (ttyUSB0): device state change: 1 -> 2 
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  (ttyUSB0): deactivating device (reason: 2). 
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  (wlan1): writing resolv.conf to /sbin/resolvconf 
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  Policy set 'Auto ucswap' (wlan1) as default for routing and DNS. 
Apr 24 14:13:43 swbr1435l NetworkManager: nm_system_device_flush_ip4_routes_with_iface: assertion `iface_idx >= 0' fa
iled
Apr 24 14:13:43 swbr1435l NetworkManager: nm_system_device_flush_ip4_addresses_with_iface: assertion `iface_idx >= 0'
 failed
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  Unmanaged Device found; state CONNECTED forced. (see http://bugs.la
unchpad.net/bugs/191889) 
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  (ttyUSB0): device state change: 2 -> 3 
Apr 24 14:13:43 swbr1435l NetworkManager: <info>  Unmanaged Device found; state CONNECTED forced. (see http://bugs.la
unchpad.net/bugs/191889) 
Apr 24 14:15:15 swbr1435l dhclient: DHCPDISCOVER on eth1 to 255.255.255.255 port 67 interval 8
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Activation (ttyUSB0) starting connection 'Vodacom' 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  (ttyUSB0): device state change: 3 -> 4 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Unmanaged Device found; state CONNECTED forced. (see http://bugs.la
unchpad.net/bugs/191889) 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Activation (ttyUSB0) Stage 1 of 5 (Device Prepare) scheduled... 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Activation (ttyUSB0) Stage 1 of 5 (Device Prepare) started... 
Apr 24 14:15:15 swbr1435l NetworkManager: <debug> [1240575315.587395] nm_serial_device_open(): (ttyUSB0) opening devi
ce... 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Activation (ttyUSB0) Stage 1 of 5 (Device Prepare) complete. 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  (ttyUSB0): powering up... 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Registered on Home network 
Apr 24 14:15:15 swbr1435l NetworkManager: <info>  Associated with network: +COPS: 0,2,"65501",2 
Apr 24 14:16:17 swbr1435l NetworkManager: <WARN>  dial_done(): Dialing timed out 
Apr 24 14:16:17 swbr1435l NetworkManager: <info>  (ttyUSB0): device state change: 4 -> 9 
Apr 24 14:16:17 swbr1435l NetworkManager: <debug> [1240575377.000361] nm_serial_device_close(): Closing device 'ttyUSB0' 
Apr 24 14:16:17 swbr1435l NetworkManager: <info>  Unmanaged Device found; state CONNECTED forced. (see http://bugs.launchpad.net/bugs/191889) 
Apr 24 14:16:17 swbr1435l NetworkManager: <info>  Marking connection 'Vodacom' invalid. 
Apr 24 14:16:17 swbr1435l NetworkManager: <info>  Activation (ttyUSB0) failed. 
Apr 24 14:16:17 swbr1435l NetworkManager: <info>  (ttyUSB0): device state change: 9 -> 3 
Apr 24 14:16:17 swbr1435l NetworkManager: <info>  (ttyUSB0): deactivating device (reason: 0). 
-----------------