Can break System Restore. Why not fix that first? It could be why this happened.

As to other fixes I know of, it required a registry edit but your security software borked System Restore (well discussed area so I'll leave it at that.)

If you use Glary or similar registry cleaners along with a long list of other things you can see the right click new fail. At least the old command line MD works and most of the time the File, New menu (not the right click but the menu) works.

Given the handcuffs you put on fixing I don't think I can help, only point out what may be what broke it. And you don't want to remove the cause or use the usual fixes.