Thanks for all the feedback from Utah peeps.
I do have a good car charger (I like the iGo chargers) and also picked up an extra battery and a dock that chargers the phone and spare battery.
I wouldn't change my carrier just for the trip. Both my friend and I use Verizon. i know you can sometimes get coverage, even where the map shows none.
My guess is that within Zion and Bryce we might get a weak signal, but not enough to make using the phone worthwhile.
I am hoping to find some crazy spot where you get a couple bars so I can do live streaming video with Ustream from my Droid.
I will probably also get the data tethering plan for the month so we can have internet on the trip out and back on the laptop.