SSH MITM attack ?

I’ve experienced an usual problem while setting up my Cent OS 7 server. Once I copied my pub ssh key from my local computer to the server, I logged in and was greeted with:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the RSA key sent by the remote host is

Please contact your system administrator.

etc etc etc...

What makes this usual is that not every ssh connect attempt will present this message :?:

I don’t have much experience so I google and found ssh-keyscan. This presented the following output:

Michaels-MBP:~ michaelr$ ssh-keyscan <ip address="" removed="">
# <ip address="" removed=""> SSH-2.0-OpenSSH_6.6.1
no hostkey alg
# <ip address="" removed=""> SSH-2.0-OpenSSH_6.6.1
 <ip address="" removed="">ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCenbCe65MnUEEmQYaotzmKJC8dg3RzYXYEn1kFFpT/UwTzb+tG9SqTEAXXZOg8ZCEOY+mu5yXHPt0zl2XCR3Y5gVtoMpL6l93fj/SkZbz6B8BGvocP6DfdG4js+qffT+BCGgThRxpIC3k10Gh4LqN8N/nPM24V7MjBWkvSzaVOyG7Gs7RM6J4cIcgYFN186PMSWD0+/rlsyVLGJBmjJEu4SiPrEClc2qsQLoyzvMY1R+osXlCrMTL3D3gzcknsG5gSW3+HPVnR4wxnDvwmpzsZxzoSvyXCJRSZX0pSWP7/AkbVP2VpCT4GuN/ddysGxqd0RYWrlKGe1vZfKrGzJuFB</ip></ip></ip></ip>

and the next time I run the command… different:

# <ip address="" removed="">SSH-2.0-OpenSSH_6.0p1
 <ip address="" removed="">ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDXo4YICgKfAHyI3H9YugtBBcsWk6jrehjBpDubnnCT3B56P8GWr6UrVz/Llr+Uvt6LDcJFPyQQclvgoz7YaPyjY3e50VzyTrETo4YXVkUiyiZ5l8yPh/ysSFAki628133PO5aKzojjSZOsZMiiwvpRbc+v+9BVBELHuQCpZrD9Ty87CB+O6XcSB7DyRgEOnrmtKTZGzux0aDGNXVOVGRKcPCIWHhIDymwLa3NV+bscNWa4Q3freB6qrxn0oebcvJrSNr//2hrPIHZbeaE47l6r3VrlY4PddpYNcIDg5smiaOLjiUJzohDTVkc/tCzz3Lf0eggZ05Mcq3fdZiiuANpR
# <ip address="" removed="">SSH-2.0-OpenSSH_6.6.1
no hostkey alg</ip></ip></ip> 

Notice the two different SSH versions. SSH in debug mode also shows the two different SSH server versions.

debug1: Local version string SSH-2.0-OpenSSH_6.2
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.0p1
debug1: match: OpenSSH_6.0p1 pat OpenSSH*

debug1: Local version string SSH-2.0-OpenSSH_6.2
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6.1
debug1: match: OpenSSH_6.6.1 pat OpenSSH*

The of the two server finger prints:

b6:e6:7a:47:e7:b7:46:2e:f6:3b:ba:7b:08:76:29:4e and 92:e7:f4:1c:26:c8:b0:51:77:71:29:03:f3:92:5e:4e.

Only the second hash is from any pub key in the ssh server directory.

This was from a clean install. I’ll probably just blow away the instance, but I'm wondering if this is a configuration error or a MITM attack.