Gracias Cantos, ya lo solucione. Me diste una idea para buscar en google y encontre el siguiente enlace:
http://www.droidviews.com/your-32gb-...how-to-fix-it
Ahi aparecen dos metodos, El primero que entiendo es usando recovery (como tu lo proponias) y el segundo es haciendo una instalacion de fabrica y aplicando varios "fastboot erase...", Pero antes de todo eso leyendo los comentarios, hay un comentario que dice que solo haciendo un reseteo de fabrica desde ajustes se le soluciono, asi que antes de hacer una de esos dos metodos, hice el del comentario y se soluciono el problema con el almacenamiento, ya me aparecen 24.89GB que seria lo correcto.
Nuevamente, muchas gracias por la ayuda.