Okay, thanks to both. Got that working. Should have known you had that in one of your plugins - but it was fun figuring the rest out
It was necessary to put the rebuild_menus into initialization complete otherwise I would get:
AttributeError: 'Main' object has no attribute 'tool_bar'
I'm using the check if the icon is in the bar before refreshing it, and then just running self.gui.tool_bar.build_bar() since I don't actually change the submenus in my plugin just the icon, although I'll put them in the code as comments so I don't forget if I ever due change the submenus.