Problems were found with the partition map which might prevent booting

I had an issue with my startup SSD media after a power failure. Running First Aid on media (the volume appeared to be ok), I got this message: "First Aid found corruption that needs to be repaired. To repair the startup volume, run First Aid from Recovery. Click Done to continue"; opening the details, it appeared to be an issue with the partition map: "Problems were found with the partition map which might prevent booting".

The problem persisted even after rebooting form USB Recovery/Installer, from another System disk. etc.: First Aid was unable to repair it.

I solved the issue by launching Disk Utility from another System Disk/USB recovery/Installer and adding a new small partition to the broken disk (I just used some disk's free space to create the new partition so I didn't need to format or re-initialize the drive). This operation overwrote the partition map and, when I rechecked the media with First Aid, the problem was gone. Then, I deleted the small partition I had created and voilà.

Hope it helps.