En mi caso el problema fue el mismo y ocurrió después de hacer un downgrade del lollipop realmente lento a kitkat y volver a rootear. Formatear o resetear de fábrica no sirvió de nada. La solución fue arrancar en recovery (TWRP) después de flashear una ROM y rootear, y allí cambiar el tipo de sistema de archivos. Por ejemplo cambié del ext4 reconocido de 8GB a FAT (esto cambió la capacidad a 32GB) y luego de nuevo a ext4. Esto obviamente borra todas las aplicaciones y datos.
Modelo: Nexus 7 (2012) WiFi, TWRP versión 2.8.6.0
Procedimiento detallado: En el inicio de TWRP, elija la opción "Wipe", luego "Advanced Wipe". Ahora, de las particiones disponibles, seleccione sólo los datos y pulse "Reparar o cambiar el sistema de archivos". La siguiente pantalla muestra la información del sistema de archivos actual, donde puedes tocar "Change File System", luego elegir el deseado y deslizar para aplicar este cambio. De acuerdo con mis instrucciones anteriores, puede repetir este procedimiento dos veces, una para cambiar a FAT y otra a ext4.