community.linuxmint.com

Works perfectly every time using Sakis3g.

Is only sometimes successful connecting with NetworkManager - when you right-click NetworkManager icon the "Enable Mobile Broadband" option only sometimes appears for you to click and connect.
Doesn't matter how long you wait.

EDIT: January 2012: updated Network Manager from 0.8 to 0.8.4.
Uninstalled network-manager and network-manager-gnome from Synaptic Package Manager.
Added the network-manager daily build ppa for ubuntu lucid main from
https://launchpad.net/~network-manager/+archive/trunk and updated.
Since then Network-Manager is showing the "Enable mobile broadband" option when I plug in the modem more consistently. It it doesn't appear, I enter in a terminal: sudo killall modem-manager
... wait ... then it usually appears.

See forum thread: http://forums.linuxmint.com/viewtopic.php?f=53&t=89232
post #7 for sakis3g solution (for me, anyway - YMMV).

ISP: Telstra (Australia)
APN: telstra.internet

NOTE: This is for Telstra PREPAID mobile broadband
NOT Bigpond internet plans - different APN