Clustering is an explorative technique, it is subjective what is good, and the best clusters are those that are "interpretable but unexpected", a property that you cannot quantity with statistics. So it is a trial-and-error task.
Furthermore, data preparation is much more important than the choice of clustering algorithm. On badly prepared data, none will work.
Last but not least, categoricial data is a huge problem. It lacks detail for most clustering approaches - treating this as binary variables is much too coarse and tends to produce bad solutions (such as tiny "clusters" and trivial splits on a single variable). This is likely a problem of the data, not the algorithm. Similar issues can be seen with integer attributes or any other attribute that has only very few discrete levels (including Likert-like-scale questionnaires). Methods such as k-modes exist for categoricial data, but often don't produce better results either...