In my experience, promises can be more difficult to debug (once the promise library takes my callback, I can't follow the flow of execution until it is called, unless I crack open the library itself), and are less intuitive. While those shouldn't disqualify the idea immediately, it does make me hesitate.
And I'm not sold on the benefits to error handling either. In the author's example, yes, all those error handlers could be grouped together - but how often do you have that many async function calls with identical error handlers? In most situations, that is a warning sign that you aren't handling errors properly and with enough "resolution".
All that said, I don't think promises are useless. There may be times when it makes sense to use them. But calling them the "next great paradigm in JavaScript programming" seems like a bit of a stretch to me.