I have not reinstalled or in any way changed my server's key. Is there a way to check whether I'm connecting to the real server or a spoofed one?
If the key and hostname on/of the server hasn't changed, then you are connecting to the wrong server. If you need to check whether the key really did change, you need a different mechanism to access the server, perhaps someone with local physical access to read the fingerprint to you. If they have physical access, they can typically get on the OS. Some hypervisors even just have root run a command and give you a root shell on the OS.
If I do accept this new fingerprint, and connect to the server, what are the potential risks?
You risk giving your authentication credentials to someone else's server, thereby allowing someone else to access your server as you. You also enable this "someone else" to MitM your connection to your server, and monitor what you do from now on.
How would I quickly find out whether there is a man in the middle of our communication?
Assume there is once you see the "key does not match" message. Only once you've proven that the key really has changed on your system (as described above in this answer) should you assume that there's no MitM or DNS error, or other problem in the communication path.
~/.ssh/known_hosts
has not been changed from the times I logged in before. – mart1n Jan 8 '14 at 17:03