While the US does have a lot of no cell zones, those areas do have coverage. I wonder if your phone operated on GSM bands that didn't cover those areas. For a while in it was pretty common that if you wanted coverage in rural areas you opted for Verizon's CDMA network.
Driving from LA to SF via the 1 very definitely has areas with no cell coverage, it's a drive I make semi-regularly (a tiny leg of the my Seattle-LA treks), and there are many patches with no coverage, especially in big sur.
From the map, Europe has 0 cdma tower while US has pretty significant number of cdma towers. Maybe most european cell phones simply doesn't have cdma support which makes roaming to US difficult?
Edit: Glancing at the map, it seems no one use cdma anymore except a handful of countries like US, Japan, Korea, Indonesia, Venezuela, and some part of North Africa.
