The solution was to use the Ease US Partition Master free edition. You have to download the free edition from the comparison page, otherwise they want to make you download the free trial to the pro version.
I connected the HDD to another computer, ran the Partition Tool from there, and then selected "Drive -> Rebuild MBR". After that I had to click on "Apply", plug the HDD back into my computer and everything was OK.
Here's the link to the page where they explain how to do this, together with screenshots and additional info.
I'm not associated with them in any way. Hope this doesn't break any rules, I'm posting this only because it solved my issue, and might help others as well.