Contact Types Not Updating in Main Menu
Thanks for reporting this and describing it so clearly. I have reproduced this problem on the latest version of CiviCRM, though in my testing I found the problem to be limited to editing the label of existing contact types (adding new contact types work okay in my testing).

Bug

This looks like a bug to me. I would suggest you take this a step further by filing a bug report. You can use the text you wrote already and even link to this page too.

Work-around

In the mean time, if you're still in the process of configuring CiviCRM (and haven't yet created contacts with your desired sub-types), you can delete those problematic sub-types and create new sub-types for "Member", "Intern", and "Staff".