I also agree with Robin, that a key question here is whether we suspect our data to be structured hierarchically (i.e., do we care about the tree); and if so, what is the appropriate number of clusters.

However, based on vague intuition, I think that if their method was compared to a method which combines a hierarchical approach with the flat k-means approach they would lose. For their procedure must maintain a hierarchical structure, whereas a combined approach is allowed to relax this constraint. Since the metric they use to compare methods is the k-means cost function, it seems that a method that is allowed to minimize this cost function directly without constraints during part of its procedure should beat their method.