First off, the hardware does work out of the box, it's just NetworkManager which doesn't know how to talk the right AT commands. The solution is quite simple. You can check if yours is working with the following commands (key bits highlighted):

singe@blackguard:~$ cu -l /dev/ttyACM0
Connected.
AT&F
OK
AT+CFUN=1
OK
Disconnected.
singe@blackguard:~$

The device is ttyACM0. AT&F will initialise the device (same at ATZ), and AT+CFUN=1 will turn the device on. You will know it has worked if you see the WAN light come on under your screen.

Now that we know it's working. I chose to use gnome-ppp to set up the connection. You can use your favourite ppp dialer (e.g. wvdial) to do the same. You'll need to install it with 'sudo apt-get install gnome-ppp'.

Once you're running gnome-ppp. Enter the following settings in the GUI:

username: anything
password: anything
phone number: *99#
Setup->Device: /dev/ttyACM0 (click detect afterwards)
Setup->Device->Init Strings
Setup->Device->Init Strings->init2: AT&F
Setup->Device->Init Strings->init3: AT+CFUN=1
Setup->Device->Init Strings->init4: AT*EIAPSW=1,1,"<apn name>"

This last string defines the APN name. If you are connecting to normal 3G, your APN name will be 'internet'. If you use a custom APN, then change as appropriate.

That's it, close the dialogs, click connect and you're done. Easy as pie.