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.