I have been looking on the web for a cellular shield that would with Verizon/Sprint. I have had no success so far. Can any one out there tell me if they know of one. I presently use the Itead SIM900 shield that works fine with AT&T and T Mobile. I tried the SIM5216E but Verizon doesn't like it.
First thing you have to be sure about is the operation frequency of the module.
A quad-band module works with GSM 850MHz, EGSM 900MHz, DCS 1800MHz and PCS 1900MHz.
If you are sure that your carrier and module are compatible, the problem might be configuration.
Try to configure APN, some carriers needs it.
I have been using Quectel modules with no problems. Even I developed a board with the Quectel M66 module. You can take a look here: MobileNode: GSM/GPRS and GPS/GLONASS 7cm circular board. - Products and Services - Arduino Forum
Verizon is very different CDMA technology and not at all interoperable with GSM phones or modules. At least here in Vermont USA..