I also travel quite a bit with work. I currently have Cingular for my personal cell service and I use AT&T through work. Previous to Cingular, I had Sprint. I had heard horror stories about Sprint's customer service, but I could not have been happier. Sprint's service was great and I never had an issue with customer service. When my contract with Sprint was up, I did give them a shot to offer me a fair deal on the Treo 600. I was surprised they would let me go without matching the offer I got with Cingular. That aside, I go with Sprint any day of the week. I might even jump from Cingular when my contract expires on my 600. I thought Sprint's coverage was fantastic when travelling and was much better than AT&T. I always had coverage wherever I landed...because I would check my email the moment I landed.
