Following the purchase of divested Alltel you should have AT&T UMTS 3G essentially the entire way from SLC to Vegas, except for in a small section of Nevada. Something is definitely wrong with your device if you didn't have 3G basically everywhere in Utah. Going north, especially to Boise, you'll have a large part of Idaho with GSM only, but again the vast majority of the trip (including all of Utah!) should have UMTS.
I am wondering if your device wasn't connecting to UMTS850 properly, and thus you were only getting coverage in cities (where AT&T used both 850 and 1900).
P.S. Your closing is just downright troll bait. "Nations best network" my backside. It's all about where you live. Here in Montana I have speeds that blow away Verizon, dramatically better coverage (and AT&T just got a large chunk of a main highway that's never had any cell service before covered!), and much better network reliability. Just today I listened to a friend (on Verizon) whine about having to resend all their messages several times. When I suggested he switch to AT&T, he said he needed the best coverage he could get and he'd heard how bad AT&T was. I told him the REALITY . Verizon's going to get a lot worse around here next year too, when they lose roaming on the old Alltel CDMA system (bye bye service in quite a few little towns...). Though they'll be faster too with LTE. Still, I'll take twice the coverage over a bit faster. 4-5mbps on my smart phone (in Helena, sadly Kalispell's more like 2-3mbps) is plenty fast enough for a phone!