You are a wordpress.org veteran! When I logged on today my post was all the down the stack, couldn't find it. Do you accept donations?
Anyway, your advice worked!
I tried logging in after step 1 and it worked. Does this mean I won't have to do step 2 or will I run into problems then again?
For reference sake, anyone else that has this problem, here's how I fixed it (although your configuration may be different, I am on DirectAdmin, others may be on Plesk, etc.):
1) Go to the URL Andrea mentions;
2) In DirectAdmin I logged in as admin (you should have this information from your host, we're on a dedicated server);
3) In the section 'Extra Features' there is a link called 'Custom HTTPD Configurations' that I clicked;
4) In the page that opened I clicked our domain name;
5) In the next page that opened I entered the contents of the link Andrea provided, replacing the 'example.com' with our domain and saved the file.