Not sure if you have resolved this.
In the user's Privilege Set, look at the "Available Menu Commands" and make sure this is set to "All".
Thank you for posting. I figured this out on my own yesterday. It is good to know that new priv sets by default are set to Minimum. Which I think is very bad. I'm sure I'll get burnedon this again.