K-NN or matrix factorization for discovering correlated features?
You're asking essentially a modelling question, and so the answer really depends on your data. If you're saying that strong correlations are not being identified by the methods you listed, it's possible that the correlations are non-linear (the above methods with the exception of k-NN are linear), and so you might try something like ICA. 

For something closer to home, have you considered correlation clustering ? you don't say how the data is presented, but if you have similarity and dissimilarity information, then correlation clustering is a good solution, and also does not require you to specify the number of clusters. 

Another idea would be to try spectral methods (if all you have is a distance function) like spectral clustering.