Project admin does not see the option to create a new template for User Stories. He has already cleared his browser cache, logged out and back in to Rally, and tried using multiple browsers.
If you look at the story behind it, it says "New Item" - meaning the story hasn't been saved yet.
Please note the wording, "Use the Templates button on an existing object to create one".
Now I've created the story - I see "US3864", this happens when I add information to the story and click the Save button. Now the templates screen shows the "New Template from US3864" message.