Проблема известная.
Умные люди в такие ситуации не попадают, сразу покупая не автоматические, а полностью механические, то есть открывающиеся вручную крепления (такие модели есть и в стандарте NNN и в стандарте SNS).
Если же вы пали жертвой экономии, погоды и невезухи, то рекомендации следующие. Самый простой и действенный способ - размочить крепления горячим чаем из термоса. Но на покатушках недалеко от дома такой роскоши может и не быть с собой.
Суть проблемы в том, что лед забивается под резинку-флексор и не дает смещаться подвижной защелке, которая держит ботинок за скобу. Надо попытаться выковырять лед оттуда, тогда крепления откроются. Возить с собой отвертку на такой случай - правильное решение, но на крайняк сделать юто можно и штычком лыжных палок.
Так что - удачи вам в борьбе с креплениями-автоматами!
Но все-таки настоятельно рекомендую перейти на ручные - это на порядок надежнее, а стоит всего рублей на 500 дороже.

Почитайте на досуге статейку, авось пригодицца:
http://tourism.bmstu.ru/index.php?option=content&task=view&id=503&Itemid=27

Таки дела...