My SPD shoes + cleats won't clip in to my SPD pedals I purchased some touring shoes (Giro Republic) that support a two bolt cleat. I opted for a standard, popular Shimano M520L pedal with matching cleats.

I installed the pedals, loosened the tension on the clip mechanism, and install the cleats with the triangular end facing forward.

Unfortunately, I can't clip in. It appears that the rubber pads surrounding the shoe make contact with the pedal axle before the cleat can engage with the back of the pedal. Note the forward part of the cleat is hooked into the front, as expected. The rear is sitting on top of the sprint mechanism.

My question is, is there something I am doing wrong in my install process? The dealer indicated they have not had reports of incompatibility between this particular shoe and cleat.
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.