я не думаю что телефон стал бы тормозить из-за забитых ячеек для смс, такое сообщение могло быть следствием глюка внутренней софтины телефона, подобное видел когда-то на 3210, 3310, может ему в телефонную поликлинику надо...
что же до карты, попробуй всякие програмки по восстановлению данных со сменных носителей типа этой:
http://www.imho.ws/showthread.php?t=...highlight=easy
умеет восстанавливать с отформатированых, "поврежденных" карт.
но прежде все-таки воткни все-таки карту обратно в телефон и посмотри на его реакцию - сможет ли прочесть то чт отам было.