public key not found, but it is there!

[Felipe Alvarez]

Hi
I am trying to play around with keys Alice and Bob for showing to my
employer on how to improve security.  "Alice" is the employer, and
"bob" the employee.

I created a key for each, on separate machines. Alice runs RedHat 4,
and gpg v1.2.6. Bob runs Cygwin and GnuPG v.1.4.11.

Alice's key was giving problems, so, on Alice's machine (which
contains her private key), i did `rm -fr $HOME/.gnupg`, then generated
a new key.

On Bob's machine, I deleted Alice's key (using WinPT's GUI interface,
which should not matter much), and imported her "new" public key.

now, whenever I try to encrypt to user "alice" It fails, saying
    encryption failed: public key not found

The public key is there! But it has a different fingerprint
(17D11744). GPG is looking for Alice's Old hash fingerprint
(DE0155B3). How can I remedy this?

----
felipe at felipes /cygdrive/C/Program Files/GNU/GnuPG
$
felipe at felipes /cygdrive/C/Program Files/GNU/GnuPG
$ ./gpg --list-keys
C:/Documents and Settings/felipe/Application Data/gnupg\pubring.gpg
-------------------------------------------------------------------
pub   2048R/1A80C23E 2011-04-07
uid                  Bob Fresh <bob.fresh at example.com>
sub   2048R/402C0B65 2011-04-07

pub   1024D/17D11744 2011-04-14
uid                  alice fresh <alice.fresh at example.net>
sub   2048g/C2509E95 2011-04-14


felipe at felipes /cygdrive/C/Program Files/GNU/GnuPG
$ ./gpg -r alice -e random1
gpg: DE0155B3: skipped: public key not found
gpg: random1: encryption failed: public key not found

felipe at felipes /cygdrive/C/Program Files/GNU/GnuPG
$

---
thanks
I am not subscribed to this list. Please reply-all!
felipe