I will start by saying I think I know what caused this boot-time error on Linux Mint but should also apply to Debian and Ubuntu.
I changed my BIOS time to several hours in the past to match the current time, but this caused Linux to think there were incorrect filesystem times.
The problem is that it seems when you hit this I am not sure what is happening, it doesn't seem to be doing fsck and hangs without prompting the user.
What I have found is that you can usually hit "S" to skip fsck or "Y" to try and fix it and it may boot. It did in my case but X did not start probably because fsck did not complete.
So I rebooted and then got the error "Starting Enable Remaining Boot-Time Encrypted Block Devices" but it hangs there too for ages not seeming to do anything. I think I hit "S" and was given the option to fsck so I said yes and this fixed it all and allowed boot to complete. I did have to ignore mounting /tmp to get there though.
Another solution is that for some there are bad fstab entries causing the issue but that was not my case.
I am fairly comfortable with Linux/Debian but this threw me for a loop, the problem is that it is not obvious what is happening and it is hard to get prompted to fsck, there should be a definitive action or prompt to ask you to fsck or not etc....
errors, disk, linux, mint, debian, ubuntu, bios, incorrect, filesystem, doesn, fsck, hangs, prompting, user, quot, rebooted, enable, remaining, encrypted, devices, seeming, mounting, tmp, fstab, entries, prompted, definitive, prompt, etc,