What do I do when I get a potential man-in-the-middle attack warning while using ssh?

See the FAQ entry "Remote Host Key Identification has Changed" error. How do I fix this?" as this also can happen when using a Terminal on Linux and connecting to another system via SSH.