There are 100s of different clustering algorithms, so when you use different algorithms, you often obtain different results.
From a statistical standpoint, we have found that the cluster ensemble approach is superior to traditional K-means for recovering "true" structure from datasets built with known true group membership. Our CCEA Technical paper describes those experiments.
But, cluster segmentation analysis is a lot of art in addition to the science. You have to find a segmentation scheme that is useful from a managerial perspective. It is quite possible that inferior clustering methods (from a statistical standpoint) may for a particular data set give a result that to the human eye seems more managerial useful.
There are also different pre-processing steps you can do that affect the final solution: choice of input variables, choice to standardize or center input variables. So, if you don't like a particular solution, you can think about whether a different pre-processing step is justified or hopefully a better way to prepare the data.