How can I make k nearest neighbor queries fast on unit hypersphere?
As a rule of thumb, when the number of dimensions $n$ is less than about 10, fancy data structures (like k-d trees) work well; when the number of dimensions is greater than about 30, fancy data structures typically perform poorly and may be no better than a brute-force linear scan.  Wikipedia lists a similar rule of thumb: if $m \gg 2^n$ (where $m$ is the number of points in the data structure and $n$ is the number of dimensions), then k-d trees work well, otherwise they won't.  Exceptions exist, e.g., where your data is "structured" and non-random, but this is probably a good first guideline.

In your example, the number of dimensions is at least 100.  Therefore, I wouldn't expect any of the fancy data structures (k-d trees, M-trees, etc.) to be better than the simple linear scan.

Essentially, you are suffering from the curse of dimensionality.

You mention that your points are all on the surface of the hypersphere.  Unfortunately, this doesn't help much.  Heuristically, points on the surface of a $n$-dimensional hypersphere are a lot like points in a $n-1$-dimensional space.