I think I know what happened.
I threw away the menu I was working on, created a brand new menu, keeping all of the normal defaults, and I was able to set the label without any errors.
What was causing the error was an extra level in my menu structure. I was experimenting with making a sitemap, where all of the menu items were in a single dropdown comprised of several columns…So I had tweaked the previous menu such that it had more than 2 levels. It looked like this:
Main Level
Column 1
Page AAA
Column 2
Page BBB
Column 3
Page CCC
Column 4
Page DDD
Nothing in the UI prevented me from creating this structure, but the API didn’t like the extra level. When I removed the extra level, the API worked without errors.
It seems like it should not be possible to use the UI to create something that is invalid, or the API might be a little more robust if these kind of menu structures are allowed…so maybe this is something that the Wix dev team might consider looking at.