Hmmm.... I spend my life in some pretty marginal signal areas, and, as long as it's digital, I've been able to establish a data connection. Two friends have even claimed to be able to establish a data connection in analog areas, as long as the signal is strong-- but I've never seen it, so I'm not believing it till I see it!

I'm not sure if it has anything to do with which Verizon market you're in, and what legacy systems they've strung together. I'm surprised there isn't data somewhere like Oklahoma City, but it may be that the carrier they've made arrangements with for coverage there doesn't support it.

One thing that happens to me a lot is that I'm between two towers, and one is sending me digital and one analog signal, so my data connection drops out. If I go in and force digital on the phone, I can hold a connection. (But be sure to set if back so as not to miss calls.) Most of my worst coverage has been in my home state, I've had great signal almost everywhere else I've travelled.