I would recommend updating your prefered roaming list (*228 option 2) this has helped me in the past.
It may also be a case where Sprints signal is stronger than Verizons where you are located. I also have a iPhone (I am on Verizon) and here in the Mpls/St. Paul area my cousin (he is on AT&T) gets a poorer signal. However, when we travel to his home in northern Minnesota, he gets better reception while I still get about the same reception. And Sprint is not even a viable option in outstate Minnesota (at least according to the coverage map). My point being that reception is not the same everywhere for different carriers even with the same phone type.