I had this problem under Karmic. Then under Lucid everything seemed to work fine, until yesterday ...
I tried following Damjan's instructions in #68, but they didn't work for me:
 * I added the rule to /etc/udev/rules.d and did a reboot
 * On plugging in the device, it seemed to initialize OK (light went flashing blue), but I could not see any 3G options under the NetworkManager menu
 * I then tried killing udisks-daemon and upowerd. After that, I plugged in the device again. This time, it showed up under NetworkManager and I got a successful connection
 * Based on the logs (see below), it seems that until I killed udisks-daemon and upowerd this wasn't registered as a GSM modem. But I didn't do a manual modprobe usbserial, that was loaded automatically, but only after killing those processes

Here's /var/log/messages from plugging in the device (initial timestamps and machine name stripped):
 [  419.520174] usb 6-2: new full speed USB device using uhci_hcd and address 2
 [  419.678471] usb 6-2: configuration #1 chosen from 1 choice
 [  419.742527] Initializing USB Mass Storage driver...
 [  419.744210] scsi5 : SCSI emulation for USB Mass Storage devices
 [  419.744536] usbcore: registered new interface driver usb-storage
 [  419.744542] USB Mass Storage support registered.
 [  419.784205] usb 6-2: USB disconnect, address 2
 [  420.520193] usb 6-2: new full speed USB device using uhci_hcd and address 3
 [  420.677333] usb 6-2: configuration #1 chosen from 1 choice
 [  420.691347] scsi8 : SCSI emulation for USB Mass Storage devices
 [  425.696685] scsi 8:0:0:0: CD-ROM            HUAWEI   Mass Storage     2.31 PQ: 0 ANSI: 2
 [  425.719657] sr1: scsi-1 drive
 [  425.720083] sr 8:0:0:0: Attached scsi generic sg2 type 5

The following are the processes I killed (didn't seem to be polling sr1):
/usr/lib/udisks/udisks-daemon
udisks-daemon: polling /dev/sr0
/usr/lib/upower/upowerd

Here's /var/log/messages after killing them and plugging in the device again:
 [  791.452167] usb 6-2: new full speed USB device using uhci_hcd and address 6
 [  791.608408] usb 6-2: configuration #1 chosen from 1 choice
 [  791.612235] scsi13 : SCSI emulation for USB Mass Storage devices
 [  791.952146] usb 6-2: USB disconnect, address 6
 [  792.248182] usb 6-2: new full speed USB device using uhci_hcd and address 7
 [  792.405485] usb 6-2: configuration #1 chosen from 1 choice
 [  792.422272] scsi16 : SCSI emulation for USB Mass Storage devices
 [  792.462390] usbcore: registered new interface driver usbserial
 [  792.462995] USB Serial support registered for generic
 [  792.463155] usbcore: registered new interface driver usbserial_generic
 [  792.463160] usbserial: USB Serial Driver core
 [  792.482663] USB Serial support registered for GSM modem (1-port)
 [  792.482788] option 6-2:1.0: GSM modem (1-port) converter detected
 [  792.483592] usb 6-2: GSM modem (1-port) converter now attached to ttyUSB0
 [  792.483621] option 6-2:1.1: GSM modem (1-port) converter detected
 [  792.483732] usb 6-2: GSM modem (1-port) converter now attached to ttyUSB1
 [  792.483767] usbcore: registered new interface driver option
 [  792.483772] option: v0.7.2:USB Driver for GSM modems
 [  797.426304] scsi 16:0:0:0: CD-ROM            HUAWEI   Mass Storage     2.31 PQ: 0 ANSI: 2
 [  797.449205] sr1: scsi-1 drive
 [  797.450346] sr 16:0:0:0: Attached scsi generic sg2 type 5