Thanks everyone for your valued input. We are now back up and running.

It seems that we had an issue with an incomplete update, so having re-installed the major update it then allowed us to remove the offending KBs. Hopefully Microsoft will release a patch in the next few days.