My SPD shoes + cleats won't clip in to my SPD pedals
Generally the cleats come with some shims for exactly this problem. If you have the box with the original pedals look around for some thin cleat shaped shims. 

If you can't find them, you can hand make shims out of plastic milk bottles, or ask around at the dealer to see if they have any spares handy.