Tried changing from UTF-8 to ISO-8859-1?
Probably I shouldn't do that as the new standard is UTF-8 for Wordpress and if I change I wonder it it will break my new posts... Has your site moved to a new server?
Possibly, it's the sort of thing the do and don't inform their customers. Is there a way to change the MySQL default?