Trying to Classify MNIST where pixels are shuffled with a seed.Why is it not working?
A good indication, although quite rough, if an algorithm is capable of solving a task (especially pattern recognition tasks) is to check if humans can. We evolved to be quite good at it.

Obviously, that might not always be true. But in your case, by shuffling you loose all the structure of the data. The only possible feature your ML algorithm can use is the number of pixels set vs unset (or the pixel values, for grayscale images), thus basically losing all the structure. The problem is that this is a bad feature since there is little correlation between the number of pixels set and the digit. There is no pattern left, and any attempt to learn a pattern is doomed to fail. Thus, your algorithm may:


try to learn a pattern where there is none
not have enough features to do the classification


or a combination of the 2.