I, too, use Alltel for internet service over cellphone. It works great (though slow @14.4kb/s) in Nebraska. Pretty much all of Nebraska, at that; Alltel has built a digital CDMA network to cover nearly the entire state.
However, once I crossed the border into Kansas, things got screwy. My Alltel plan is such that my phone should work anywhere in the country. It did get a digital signal in Kansas, and from the maps I've seen, Alltel has their own Kansas network (no partnering). However, attempting to connect to the QNC internet connection in Kansas was a no-go. The phone connected fine and would even start to get data, but the network would kick me off after fifteen seconds or so; not long enough to pull down a radar shot. I'm not sure why this is; I plan to ask Alltel about it.
From what I've read, Verizon is the real "perfect" cellular data solution. Large digital network, FAST connections in large cities, 14.4 QNC connections elsewhere, and it only uses your minutes. That, and they allow you to change your minutes plan without penalty. Bulk up in the spring, cut back in the winter. Alltel lets you do that now, too, I believe.