Что могло случится? Телефон Samsung GT-S3600 пишет что память переполнена, а на самом деле она почти полностюь свободна.

Вы и ваш телефон, видимо, имеете в виду разную память. Наверное, в телефоне заполнена системная память, в которую по умолчанию устанавливаются приложения, а много места - на карте памяти, предназначенной для пользовательских данных. Удалите неиспользуемые приложения, а заодно - лишние рингтоны и обои, которые тоже могут храниться в системной памяти. Или, если телефон позволяет, устанавливайте приложения на карту памяти.