Parece que el teléfono ya no puede conectarse a la tarjeta SD. Como esto sobrevive a un reinicio, lo más probable es que sea un fallo de hardware.
Si tu teléfono está rooteado, adb shell su dmesg
debería contener mensajes que lo confirmen.
El "almacenamiento externo" en un Nexo de Galaxy es en realidad un almacenamiento flash no removible. No creo que pueda reemplazarlo (pero podría estar equivocado).
Es posible que el sistema de archivos esté simplemente corrupto, en cuyo caso el reformateo funcionaría. Necesitas tener un dispositivo rooteado para eso, e instalar algunas herramientas adicionales de una distribución de Linux.