I assure you that the NSA has its own substantial backhaul infrastructure, so local policies don't really affect its operations in any way. I think Utah is just very politically receptive to the idea that citizens communications should be monitored. I guess sure, the NSA likes that position in general, but it doesn't really have anything to do with where they store the bits.

It's because the mormons are squeaky clean and can be trusted to deal with state secrets. Intel agencies love them for this.