Do you think that unbalanced classes is a big problem for k-nearest neighbor? If so, do you know any smart way to handle this?
In principal, unbalanced classes are not a problem at all for the k-nearest neighbor algorithm.
Because the algorithm is not influenced in any way by the size of the class, it will not favor any on the basis of size. Try to run k-means with an obvious outlier and k+1 and you will see that most of the time the outlier will get its own class.
Of course, with hard datasets it is always advisable to run the algorithm multiple times. This is to avoid trouble due to a bad initialization.