Spell checkers make use of Burkhard-Keller trees (BK-Tree) an example is found here https://github.com/mkarlesky/csharp-bk-tree. This is very fast at testing a new word against the existing list, but also giving a "distance" measure that is based on the number of operations needed to change the string to the next. Unlike a simple "contains" test that gives you a boolean, this gives you a way to organize your available options. You can read more about it here: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees. I suspect that you can use the distances to help with clustering.
I guess the main thing about bk trees is that you can continue to use the Levenshtein distance. But then maybe you were already using that? This technique isn't ideal for picking an arbitrary number of clusters like k-means does. But I did see an interesting article on taking advantage of some new parallel processing in the context of k-means that might help you speed things up in C# here:
http://www.codethinked.com/multi-threaded-k-means-clustering-in-net-40
The example isn't using strings, but I maybe the AsParallel concept will help with performance for the solution you already have?