(similar to standard hashes, The only problem, IIRC is that public key algorithms generally don't generate the same results on the same piece of text 2 times in a row.)
   That's deliberate - most PK algorithms add a salt value to the plaintext to avoid any weaknesses due to repeat-encryption. If you just do a plain PK encryption (RSA sounds like a good idea given the patent expires in about a month) then it is repeatable (for hash purposes) and decryptable given the secret key.

   If you would rather stick with something like PGP though, you could always encrypt the password when it is changed, but keep a hash of the password as well for verification.