Это связано с тем, что на внутренней памяти храняться еще какие-то данные, предположительно кэш. Часть места, видимо, зарезервировано под систему, поэтому впритык память нельзя использовать.
Решение так или иначе состоит из сброса кэша и возможной чистки, если есть рут-права. Все, что я нашел, сводится к трем пунктам:
1. Чистка кэша приложений.
2. Вайп системы
3. Вайп кэша.
Мне помогло только последнее, не знаю почему. В любом случае, CyanogenMod 12, поставленный вместо кривого стока, на это пока еще не жалуется.