I didn't want the plugin to automatically delete preexisting user accounts, so it just fails. That's about as graceful as it gets right now.  You could delete the old users, and they'll be recreated as SSO users. If you need to keep those user accounts in place (e.g: If they have posts attributed to them), you could change their WP passwords to match what the SSO plugin is expecting.

Wordpress users can't login without a password, so the plugin has to make one up on behalf of the user and log them in using that. The way it does this is by creating a SHA-256 HMAC hash of the user's login name, with the Wordpress AUTH_KEY constant as the hash password. Wordpress does some additional hashing and salting beyond that.

If you're interested in source code, the relevant lines are here:
http://plugins.svn.wordpress.org/saml-20-single-sign-on/tags/0.9.1/lib/classes/saml_client.php line 28
http://plugins.svn.wordpress.org/saml-20-single-sign-on/tags/0.9.1/lib/classes/saml_client.php line 125