So I first tried fsck in recovery mode, and it simply said something along the lines of "e2fsck : Cannot continue, stopping now".
Then I booted into the live version, and followed the method you linked to.
Since it pointed to a specific repository and Boot Repair was already installed, I first removed it then reinstalled it just in case that repository contained a slightly different version.
Boot Repair proceeded as before, stopping because of "Locked NVram".
Here's the pastebin of the log file : boot repair - Pastebin.com

I ask especially because there's another partition that do more or less match the size you described, at 128 Mb, but there's no indication on what it might be.