I think that Amazon being first in 2005/2006 helped a lot, too. Google now provides "primitives" through GCE. I think Google realizes that the future is GCE not GAE.
The narrative shifted away from PaaS for a number of reasons, but the value prop is still present.
(Disclaimer: work on BigQuery, a DBaaS, which is, in my opinion, is clearly the future)
Plenty of people in the web hosting industry offered competitive x86 linux instances or dedicated servers, way prior to 2006.
I think AMZN deserves credit for delivering a price compelling option that delivered (1) elasticity (per hour billing) and (2) automation (API, available in minutes), among other things.