Was about to post an issue but instead I have a solution!
I'm running a multisite install and just tried to use this plugin on just one of the sites. After activating on the site, I tried to add a menu but was told I didn't have the right permissions, despite being an administrator. Turns out the plugin has to be network activated, not site site activated, to get around this.
Just thought I'd post incase anyone else is having this issue.