Me da la impresión que el fsck no está corrigiendo los errores. Tienes actualizado tu Ubuntu? Creo que en algún momento hubo un bug relacionado a este tema. Por otro lado porque no pruebas arrancar con un liveCD y ejecutarle el fsck a tus particiones de Ubuntu. Saludos. 