Have found through a bunch of testing that when you add an additional custom post type, the new custom post type will show on the edit menu page.
Problem is with the initial places post type and places category. While they might be able to have the name changed they do not show up to be added into menus on the edit menu page.
Not sure if this is a bug or just a limitation.
Bill