It seems that our clustering algorithm didn't work. After trying many different combinations of parameters, (lower min_samples and higher eps should lead to more clusters) I could only ever get 1 cluster, which is useless. This algorithm must be ill suited for a dataset like this with all categorical data.
I'm starting to think that there isn't a way to cluster this dataset to match the classes. There is a good chance that the classes are spread out in separate areas of the space. If this is the case, then there would be no way for an unsupervised learning algorithm to know that these separate areas could be linked as one cluster.
We'll try one more clustering algorithm just to see if we can get some results. We'll try agglomerative clustering which is also good for non-linear clusters.