This can be repro'd locally by removing the entry for ec2-54-212-85-156.us-west-2.compute.amazonaws.com in the .ssh/known_hosts file.
In paramiko>0.2.9 there is automatic checking of host signatures. The default now is to fail when the hostname is not known. Since the travis machine is brought up empty the known_hosts will be empty. Not sure why this is a new error however.
We could add the known_hosts to the content that travis unpacks.
Larsson: Xa is out next week. Would you please find a different validator?