Less amazing is how long it took to take off once it did arrive: cost model. Calling a mobile was quite expensive in Europe, so SMS was a big money saver. While in the US calling a mobile costs the same as calling any other number (you pay, or perhaps "paid" these days, for the privilege of having your phone number on a limited-capacity radio device rather than connected to a pair of wires).
On the cost front, this isn't a flame about Europe-vs-US. But until the iPhone utterly reconfigured the mobile market, the US was a mobile backwater. I really think the cost structure and lack of competition was the reason.