You should've had roaming on either Alltel (this is now the AT&T network BUT Alltel only had GSM on about half their towers, even at that the signal was very weak, it didn't actually work right most of the time, etc. AT&T now has UMTS on every former Alltel CDMA site plus many new sites. They have not added GSM to any new sites that didn't already have GSM, but they have tweaked the GSM network so it works much better than it did) or CellularOne in both Billings and Great Falls, as well as a fair chunk of the Interstate.
Much much better now though. Native UMTS HSPA+ that is much further reaching than Alltel CDMA was or Verizon is