I know this may sound really dumb and I do not know the reason why it solves it but I found it on another thread for Arch Linux.
The solution is to open shell and "shutdown now" then when the machine comes back on then do a "reboot" and the message goes away and future reboots do not hang anymore.