Classifying partially labeled data
One way to interpret this as that it's indicating that points that are nearby in feature space are likely to have the same labels.  So, a classifier that takes this into account might do well.

Based on that, you might try a $k$-nearest neighbor classifier.  Basically, you classify each test point by finding the $k$ most similar labelled samples, and then using some kind of voting scheme among the corresponding $k$ labels.  I anticipate this might give quite good results.

Alternatively, another way to use this is to use some kind of active learning algorithm to help you choose a small subset of the 10000 samples to manually label, with the goal of choosing those smartly so those additional labels help improve the performance of your classifier as much as possible.  One standard approach is to train a classifier on the labelled instances, apply it to all the remaining instances, pick out the 20 instances that the classifier is least confident on, manually label those 20 instances, add them to the training set, and repeat.  In your situation, a possible approach is to train a classifier on the labelled instances, apply it to all the remaining instances, from each cluster randomly sample a few instances whose predicted label disagrees with the majority label for that cluster, manually label all those instances, add them to the training set, and repeat.  Or, you could train both a normal classifier and a $k$-nearest-neighbor classifier on the labelled samples, apply them to all remaining instances, find ones where the two classifiers disagree on their prediction, randomly sample 20 of them (possibly using a farthest-first heuristic to maximize their diversity), manually label them, and add them to the training set and repeat.

You might need to experiment a bit to see what works best.