You may want to check that your phone is set to automatic and not Sprint only. If verizon had signal there and you had none then your phone should have roamed onto Verizon. I have seen phones from stores in FL that go out set on Sprint only and causes those people a lot of headaches when they get way off the beaten path.
