OK, I found the problem after I walked through your steps slowly.
After pasting the key in, I was hitting save immediately (which I would suspect most users are doing). The AJAX call that validates the key is a bit slow and only occurs when you click out of the license key field. So clicking the Save button was actually just validating the license and not saving it. I was receiving the Valid Key message but never the “Saved” message. So, before I click on the Save button, I had to tab out of the license key, wait a few seconds for the validation to run and then click on save.