I just got this same issue. It seems like Pymel says the menu exists already on startup but then fails to delete it because it doesnt exist.
I didnt have any time to find a proper solution but the workaround for me was to change mgear/menu.py and put this block in a try except.

Btw, I installed it with the drag_n_drop installer. Does it make a difference to install it manually?