There's a bug in the version of openssl on Ubuntu 8.04 that means it gives false positives when verifying some certificates. This could have been oh so Not Good at All, except it got caught in plenty of time - and in future I get to ssh into a known safe box when checking certificates.
And what fun, it turns out the bug goes back at least some way towards Ubuntu's ancestral Debian distro.