I would like to use the plugin for networkwide menus

I would like to use the plugin for networkwide menus located at http://www.wpmututorials.com/plugins/networkwide-menu/ but it says "You have to be using themes that add theme support for menus" and when I go to the menu settings on the Magazine theme it says "Your theme does not natively support menus". Does that mean I can't use the networkwide menu plugin with this theme? If so is there a workaround? Maybe with a Child theme?
I could use a theme on my main site that does support menus but I would like the sub-sites to use the Magazine theme if possible.