I faced the same problem. Changing the theme did not do the trick. I had to reinstall wordpress 2.5 to another folder, then move all the necessary files from the existing folder to that new folder.
I got similar problem & I still had some errors after doing the steps described in http://www.tamba2.org.uk/wordpress/site-url/. It would not let me change the 2 fields. So I had to resort to exporting the wp_options table, modify it offline, then import it again (of course after backing up the original wp_options table). I got my formatting back after that.
