I put the right shoe into the left SPD pedal. (I know, you don't even need to say it.) It was not even attached to the bike at this time. Just took both out of their boxes and thought to self, 'how does this work?' My first ever attempt at cleats, and by the looks of things, this is possibly my last.
Do you mean it's stuck? It might not be that you've got the wrong shoe in the pedal but that it's rather stiff (the pedals seem to arrive at up with tight springs) and holding it in your hands you can't get much force. The actual cleat is symmetrical. Try putting a crank arm (or whole bike) on the pedal, and putting your foot in the shoe, then twist your foot, holding the crank or bike. It should just pop out as if it was the correct shoe.
I've got walkable SPD shoes and pedals with a cage round the SPD, which means more to get in the way. But when first setting up the cleat tension I though this would be a good idea. It's a good lesson in how much stronger your legs are than your arms.