I am experiencing something somewhat similar. I am working on a multi-language website that allows the user to switch between English and Spanish. Switching the language works on accessing the pulldown, but doesn't stick. As soon as I navigate to another page, the language selection is lost.
In trying to isolate the problem, I even tried create a new database from the setup page and switched to the default theme, and the problem persists. I regressed the installation to 1.2.9, and the problem goes away. Could there be something in the 1.3 release causing this?
Well, the language setting should be remembered by a cookie. I do not think that changed from 1.2.9 to 1.3, but of coures it is possible that something has impacted it.
At any rate, there is a define, DEBUG_LOCALE, in functions-i18n that if you set to true will record all sorts of information on how the language selection is being made.
I did find the problem. Somehow the saving of the language to a cookie was lost. That is restored in tonight's build. For the adventurous, the change is isolated to the functions-i18n.php script. That script may be used to replace the one that is included with the 1.3.0 release with no problems.