Nearest neighbors search for very high dimensional data
I hope that the following resources might get you additional ideas toward solving the problem:

1) Research paper "Efficient K-Nearest Neighbor Join Algorithms for High Dimensional Sparse Data": http://arxiv.org/abs/1011.2807

2) Class project paper "Recommendation System Based on Collaborative Filtering" (Stanford University): http://cs229.stanford.edu/proj2008/Wen-RecommendationSystemBasedOnCollaborativeFiltering.pdf

3) Project for the Netflix Prize Competition (k-NN-based): http://cs.carleton.edu/cs_comps/0910/netflixprize/final_results/knn/index.html

4) Research paper "Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data" on the curse of dimensionality phenomenon and its relation to machine learning, in general, and k-NN algorithm, in particular: http://jmlr.org/papers/volume11/radovanovic10a/radovanovic10a.pdf

5) Software for sparse k-NN classification (free, but appears not to be open source - might clarify with authors): http://www.autonlab.org/autonweb/10408.html

6) Several discussion threads on StackOverflow:


https://stackoverflow.com/questions/20333092/knn-with-big-sparse-matrices-in-python
https://stackoverflow.com/questions/18164348/efficient-nearest-neighbour-search-for-sparse-matrices
https://stackoverflow.com/questions/21085990/scipy-sparse-distance-matrix-scikit-or-scipy
https://stackoverflow.com/questions/10472681/handling-incomplete-data-data-sparsity-in-knn
https://stackoverflow.com/questions/5560218/computing-sparse-pairwise-distance-matrix-in-r (unlike all previous discussions, which refer to Python, this one refers to R ecosystem)


7) Pay attention to GraphLab, an open source parallel framework for machine learning (http://select.cs.cmu.edu/code/graphlab), which supports parallel clustering via MapReduce model: http://select.cs.cmu.edu/code/graphlab/clustering.html

You might also check my answer here on Data Science StackExchange on sparse regression for links to relevant R packages and CRAN Task View pages: https://datascience.stackexchange.com/a/918/2452.