I have had success massaging the edge of the foot (be careful not to damage the foot. Once it lifts just a bit then try to carefully massage the underneath of the foot, this is harder on rock but it can be done.
I have hear of people using ice cubes to have them release. I have not tried this method.