This happened to me as well:
http://www.dslreports.com/forum/r23502270-3G-came-on-today-but-now-1x-signal-is-terrible-Need-HelpIt was not my phone but the fact that Verizon threw me onto a Hybrid Network using both Verizon and Alltel towers and also updated my PRL and this started happening without notifying me
After a month of dealing with Verizon they finally submitted my original PRL back to my phone and locked my phone onto the Verizon network only. The "entering service area"/"leaving service area" message stopped after this.
Not saying this is what is happening to you, but you may want to see what PRL is on your phone.