A mi tambien me paso que me encontre con 23GB de espacio interno cuando fui a mirar, por suerte solo habia reinstalado algunas apps, no todas. En mi caso, la solucion que encontre fue esta:
Reiniciar en bootloader y ejecutar en una consola adb:
fastboot format userdata
fastboot format cache
fastboot reboot
