I went out and bought a Cricket a600 modem for the cases where my internet goes out. There are all sorts of howtos on getting it working, including one my friend Sean wrote. However, these were really complicated, and there's no way around that. It's not something an end-user could do.
Enter the Koala. Setting it up on Karmic is a snap. First, apt-get install usb_modeswitch. I think there might need to be a reboot in there, but I'm not sure. Then, plug in your modem, and right click on "Edit Connections..." and click on the "Mobile Broadband" tab. Add a connection, walk through it, and you'll find that Cricket is one of the options. Then that's all there is to it.
My one request is that when I plug it in, it would disconnect the wireless connection when it connects to the mobile network, just because if I'm connecting with the Cricket modem, it means that wireless is flaky. Currently, I just go up and disconnect it manually, but it'd be nice if it was automatic.