I can confirm this is a problem with the SE K850i, too. Obtained this from my logs:

Jan 16 14:33:18 mini9 NetworkManager: <info>  Activation (ttyACM0) starting connection 'T-Mobile' 
Jan 16 14:33:18 mini9 NetworkManager: <info>  (ttyACM0): device state change: 3 -> 4 
Jan 16 14:33:18 mini9 NetworkManager: <info>  Activation (ttyACM0) Stage 1 of 5 (Device Prepare) scheduled... 
Jan 16 14:33:18 mini9 NetworkManager: <info>  Activation (ttyACM0) Stage 1 of 5 (Device Prepare) started... 
Jan 16 14:33:18 mini9 NetworkManager: <debug> [1232116398.835867] nm_serial_device_open(): (ttyACM0) opening device... 
Jan 16 14:33:18 mini9 NetworkManager: <info>  Activation (ttyACM0) Stage 1 of 5 (Device Prepare) complete. 
Jan 16 14:33:19 mini9 NetworkManager: <info>  (ttyACM0): powering up... 
Jan 16 14:33:19 mini9 NetworkManager: <info>  Registered on Home network 
Jan 16 14:33:19 mini9 NetworkManager: <info>  Associated with network: +COPS: 0,0,"T-Mobile",2 
Jan 16 14:33:20 mini9 NetworkManager: Invalid byte sequence in conversion input
Jan 16 14:33:49 mini9 last message repeated 11 times
Jan 16 14:34:20 mini9 NetworkManager: <WARN>  dial_done(): Dialing timed out 
Jan 16 14:34:20 mini9 NetworkManager: <info>  (ttyACM0): device state change: 4 -> 9 
Jan 16 14:34:20 mini9 NetworkManager: <debug> [1232116460.004256] nm_serial_device_close(): Closing device 'ttyACM0' 
Jan 16 14:34:20 mini9 NetworkManager: <info>  Marking connection 'T-Mobile' invalid. 
Jan 16 14:34:20 mini9 NetworkManager: <info>  Activation (ttyACM0) failed. 
Jan 16 14:34:20 mini9 NetworkManager: <info>  (ttyACM0): device state change: 9 -> 3 
Jan 16 14:34:20 mini9 NetworkManager: <info>  (ttyACM0): deactivating device (reason: 0). 
Jan 16 14:34:20 mini9 NetworkManager: nm_system_device_flush_ip4_routes_with_iface: assertion `iface_idx >= 0' failed
Jan 16 14:34:20 mini9 NetworkManager: nm_system_device_flush_ip4_addresses_with_iface: assertion `iface_idx >= 0' failed

Running a fully patched (including intrepid-proposed) Ubuntu 8.10 i386 install. I am able to connect with wvdial/gnome-ppp just fine, including as I write this. The connection is to T-Mobile in the UK, but I'm not sure this has any bearing.

Oddly, I also have two modem devices detected: 

[ 4930.062123] usb 5-3: new high speed USB device using ehci_hcd and address 6
[ 4930.207543] usb 5-3: configuration #3 chosen from 1 choice
[ 4930.216272] cdc_acm 5-3:3.1: ttyACM0: USB ACM device
[ 4930.227198] cdc_acm 5-3:3.3: ttyACM1: USB ACM device
[ 4930.254812] cdc_wdm 5-3:3.7: cdc-wdm0: USB WDM device
[ 4930.264535] usb0: register 'cdc_ether' at usb-0000:00:1d.7-3, CDC Ethernet Device, 02:80:37:0d:03:00

Both exhibit exactly the same behaviour (as pasted above) and I'm not quite sure what the difference is. usb0 is broken in the K850i, which is a great shame: with the k800i, you can simply request a DHCP lease via usb0 and you're good to go. :(

As an annoying side effect, network manager does not include any manual control of the 'offline' mode that it extends to Firefox and pidgin (and possibly other apps.) This means that pidgin requires coercing to connect instead of simply stating 'waiting for network' when you select 'online', and Firefox requires that you un-check the 'work offline' checkbox in the File menu each time the program is loaded.

It appears that network manager was designed to be extremely pretentious in this regard; ignoring the fact that you could be connected to a network without it. I don't dislike the integration, but I DO dislike that there is no manual over-ride of the feature in network manager itself. I understand, however, that this is only a side affect of the bug in question, and should be raised as a separate feature request.

Regards,

Tom