It seems like a never-ending fight at the moment, I'm able to fix it every time it happens, but having migrated to an 18 month old SSD pulled from a different (fully working) machine, I now seem to somehow corrupt something whenever I shut down Ubuntu.
The machine will work fine for a couple of days solid running, then start behaving oddly - most recently setting the root partition to read only, mid-session. I reset the computer from the power menu, and there don't seem to be any error messages, and then when it reboots I get the error:
Error: Environment block too small. Please Press any key to continue...
Pressing any key does nothing, and so I boot to a live CD and run boot-repair, as described here:
This seems to fix it a little bit, and so I then follow the instructions on this previous answer to get my "environment block" back to normal.
Only trouble is that it only seems to last short while!