So I was struggling with a similar issue
I wanted to create lots of menus to displayed based upon permissions... lots of the items were duplicates etc so the easy way was likely to somehow copy something that already existed
I then needed to migrate all those menus to multiple blogs which share the same permissions.
But I am only a half-hearted programmer.
So this is the kludge solution but it seems to work, no programming required
WP has an export function - if you have a clean blog (and maybe even if you haven't) it seems all the menu items get listed in the same part of the export file.
There are only 2 things (possibly) if you are dealing with a single blog that need to be changed, as posts and pages will be skipped anyway due to duplicate slugs
This is the definition for the menu's custom category. You need to change the slug and the CDATA (where is says "FA" in my example)
Next you need to do a search and replace for all the menu items related to that slug / category.
<category domain="nav_menu" nicename="FA"><![CDATA[FA]]></category>
Again look for the "FA"
Save the XML with a nice clean filename.
Then you use the WP importer plugin to import the XML
YMMV but WFM and saved me a ton of time