Clipless Pedals Brand Identification
I have two pairs of shoes with different cleats - and two bikes with different pedals. Both pairs of shoes work well on one bike, but with one set of shoes the cleats jam on the other bike.  There are several brands of pedals and cleats that have varying degrees of compatibility. Replacing the rubber is unlikely to fix the problem of the cleat not releasing. 

On top of this, there is also single release (Shimano SH51 and SH52) and multi release cleats (SH55 and SH56) cleats -  Single release will let you unclip with a horizontal rotation only, where as multi release let you unclip with a diagonal, horizontal or upwards pull. 

Check you cleats - if they are single release, I would replace them with multi release as a first step. You may end up needing to try several different cleats, so a trip to the LBS might be the quickest way to find something that works. 

From SPD / SPD-R / SPD-SL cleat application table : 


SM-SH51 for single direction release,and for “Easy step-in” feature
SM-SH52 for PD-M858 and other SPD pedals except PD-7410 or PD-6500
SM-SH55 for multi-directional release except PD-M959 / M540 / M520
SM-SH56 SPD Cleat Sets Multi-directional release for PD-M959 / M540 /
M520


Wellgo also do cleats that some claim are Shimano compatible, but other's say can be hard to get out of some Shimano pedals. They come in 98A (common), 99A and also I have seen a TB51A (but its not in the catalogue). Crank Bros and Richey have cleats that look similar, no idea about compatibility.