Heh. There was a similar post quite recently and it also turned out to be a host-upgrade problem. Big name, so it may even be the same host. I'm envious. My host is HUGE and they don't seem to have upgraded yet.
Crystal ball says you've got a CMS that came with a prefabricated htaccess. It takes requests in one form and rewrites them to another form. Ordinarily the Apache version should have no effect, but there are some nasty exceptions involving exact format of paths. Or, then again, your host may have seized this opportunity to do some housekeeping, and physically rearranged everything on the server at the same time.
Before tearing out any more hair, check with the CMS itself and see if they've got an alternative htaccess for-- I assume-- Apache 2.4 instead of 2.2. And then you can post back and we'll tear the new version to pieces ;)
Just seen it prefers Example.com
Yes, often it's enough to follow the spirit of the law, but sometimes you have to follow the letter as well. A moderator will come along to fix it.