What's wrong with my implementation of the Matching Pursuit algorithm?
In MP it is very important which dictionary is used. For example, if the atoms are orthogonal The problem will converge faster.

Another interesting example, where two entries of the dictionary are the same, you can wither find both corresponding values in the sparse signal as 1 and zeros or as 0.5 and 0.5. You can find any number of representation for such an example. Which one will the algorithm converge to? 

In general, the picking of the dictionary $D$ is a very important point in the MP algorithm. I recommend you take a look in the following link as well as researching a bit more yourself. The Fourier matrix, for example, is a common choice for the dictionary. 

To answer your question, while I could not find a problem with your implementation of the algorithm, the data you are using might be problematic.