Where did you get the new theme from?

Does Firefox always return to the "Default" theme?

I think Firefox stores your theme change in a settings file named prefs.js which also stores such settings as custom home pages, changed toolbar button order, and various other settings. Are you losing any of those settings between sessions?

This article might be relevant: How to fix preferences that won't save.

Oh, since you mentioned disabling it, it sounds more like Firefox remembers the theme you chose, but it doesn't display correctly. Hmm.