No, that shouldn't happen.

It happened to me in the last to updates. But after I restart Firefox, it always comes back. Did you try that?

Firefox has been closed and restarted several times and nothing from the previous themes has returned.

In such case, you might want to post your question in Personas' forum where you will get better suggestions or help:

http://groups.google.com/group/mozilla-labs-personas

Personas are stored in a pref (about:config), so if there has been a problem with prefs resetting then you lose all personas as well.

See this article for some suggestions: Firefox says it's just updated every time it starts - how to fix

See also http://kb.mozillazine.org/Preferences_not_saved and How to fix preferences that won't save

http://kb.mozillazine.org/Themes (Lightweight theme)