How are you configuring it? I tried wvdial to configure it the first time and now it detects perfectly with the default configuration. This is in Ubuntu 11.04. It did take a lot of time initially but now it detects in seconds. Which device do you have? I recently got a Huawei EC150 whose drivers cd came with software for Linux as well. I couldn't install it as this was for x86 architecture and mine is amd64. So i suggest you google about wvdial, use it to configure it first, then add it in your default network manager under mobile broadband tab.
Sanket -- http://mm.glug-bom.org/mailman/listinfo/linuxers
