You are on the right track...it is an encoding issue. Your blog was probably latin1 and when you upgraded, then your wp-config.php file had utf8 as the encoding...however, that doesn't change the db encoding. So, you now have mixed encoding in your db. There is no simple, complete, fix for this that I have found. Here is what I would suggest.
1. If it's not already there, put utf8 in the config file as the encoding.
2. dump your database and keep it as a backup.
3. Look at your database and tables and see what their encoding is...there is a good chance that you will have a mix of encoding there as well. If you see tables or the database encoded as anything other than utf8, then make a note of it...if it's anything else, it will probably be latin1
4. Either dump the database again, or make a copy of the one you already dumped. Open it in a text editor, and do a search and replace on any encoding that you noticed wasn't utf8...for example, replace latin1 with utf8.
5. Drop your tables in the database and import the corrected sql file.
6. look at your posts and see what type of text errors you have. If you have these, Â, then do a search and replace on the dumped file, drop the tables and import again. If you have other problems, like question marks, then that's a bit tougher because you may not want to strip out all your question marks through a search and replace, so look to see if there is a pattern that you can search for. Often, you will have / that replaces ' so many of your words like Steve's will be Steve/'s. You will just have to look at what you have and use some logic to clean it up as best you can.
If you do this, you may not be able to clean things up 100%, but all your new posts should be correct and you will have a good database if it's set to utf8_general_ci encoding.