Last time I connected my phone in Kubuntu, I was prompted to set up a connection with 3G Mobile Broadband. In regular Ubuntu, I think you can do the same by clicking on the Network Manager icon in the upper panel and select something like "New Mobile Broadband connection..."

I'm not exactly sure what it's named, but I have done it before with success.