Are there any nulls in the variables that you are trying to cluster with? This suspect this might cause a "null cluster" label for any records with null values. The Field Summary tool might be handy to help you in determining this.
If you don't have nulls in the dataset, can you please post an exported copy (Options > Export Workflow) of your workflow that reproduces the behavior you are encountering? I would be more than happy to help you troubleshoot.