Un Nokia 6300 recién comprado muestra "Memoria llena, no puede recibir mensajes" y luego "204 KB necesarios. ¿Eliminar algunos datos?" sin haber guardado apenas nada. Es un fallo común de software.
*#7370#.Esto borra ajustes personales pero no elimina contactos ni mensajes guardados en la SIM. Tras el reinicio, la memoria interna debería mostrar espacio libre correcto.
Verifica que no haya mensajes almacenados en la memoria del teléfono (Menú > Mensajes > Opciones > Configuración > Memoria en uso). Muévelos a la tarjeta de memoria o bórralos.