All the presented algorithms have pros and cons. You have to understand the algorithms(tools) at your disposal and find the best for the questions you want to make.

In the K-means case, it is good to know beforehand how many groups(clusters) you are expecting. Otherwise, there are other clustering algorithms(like gdbscan) which detect the number of cluster automatically(although you have to provide the average expected density). But once again all depends on the question you want to answer, or if you are just cleaning the data a bit.

Know your data, know your algorithms and always question the results.

The paper enumerates all of the shortcomings it has. So, what more did you need? Essentially, it can be highly influenced by where the initial means are chosen and the existence of outliers. Further, on multidimensional data you have to take care in choosing the distance formula. (There was a great blog not long ago about using K-Means to find the "palette" of an image where many of these shortcomings can be seen easily.)

That isn't to say the algorithm can not be used. It just is not bullet proof.

The groups are dependent on the initial configuration. Have a look at the (poor) grouping on page 8.