I have a system running Jaunty Beta AMD64 with ssh 1:5.1p1-5ubuntu1.

I have two private keys, both of which are valid in a number of remote servers. If I copy one of the keys to ~/.ssh/id_rsa everything works correctly. If I copy the other key to ~/.ssh/id_rsa it does not work within gnome using seahorse and ssh-agent, but it does work from a non-Gnome session. Both keys work correctly in Intrepid. Both keys were originally generated using PuttyGen on Windows. Looking at the trace at the end of this response, does seahorse have an issue if the key is only 1023 bits instead of 1024?

It works from a non-Gnome session:
Ctrl-Alt-F2
Login using Username/Password, 
$ ssh server.example.com
<Enter passphrase for key /home/user/.ssh/id_rsa>
Connects correctly.

But it doesn't work within Gnome:
Start Gnome Terminal
$ ssh server.example.com
<Gnome dialog box pops up asking for passphrase>
Permission denied (publickey,gssapi-with-mic).

$ ssh -vvv server.example.com
<snip>
debug1: Offering public key: /home/user/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-rsa blen 148
debug2: input_userauth_pk_ok: fp ed:<snip>
debug3: sign_and_send_pubkey
debug1: Authentications that can continue: publickey,gssapi-with-mic
debug1: Trying private key: /home/user/.ssh/identity
debug3: no such identity: /home/user/.ssh/identity
debug1: Trying private key: /home/user/.ssh/id_dsa
debug3: no such identity: /home/user/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
Permission denied (publickey,gssapi-with-mic).

For comparison, using the same key in the terminal session (i.e. no ssh-agent, no seahorse):
debug1: Offering public key: /home/user/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-rsa blen 148
debug2: input_userauth_pk_ok: fp ed:<snip>
debug3: sign_and_send_pubkey
debug1: PEM_read_PrivateKey failed
debug1: read PEM private key done: type <unknown>
Enter passphrase for key '/home/user/.ssh/id_rsa': 
debug1: read PEM private key done: type RSA
debug1: Authentication succeeded (publickey).

Also, using the same key in the terminal session but using ssh-agent (still no seahorse):
$ eval `ssh-agent`
Agent pid 25343
$ trap "kill $SSH_AGENT_PID" 0
$ ssh-add ~/.ssh/id_rsa
Enter passphrase for /home/user/.ssh/id_rsa: 
Identity added: /home/user/.ssh/id_rsa (/home/user/.ssh/id_rsa)
$ ssh -vvv server.example.com
<snip>
debug1: Offering public key: /home/user/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-rsa blen 148
debug2: input_userauth_pk_ok: fp ed:<snip>
debug3: sign_and_send_pubkey
debug1: Authentication succeeded (publickey).

Finally, using the "good" key that works inside Gnome:
In Gnome, start Gnome Terminal
$ ssh -vvv server.example.com
<snip>
debug1: Offering public key: /home/user/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-rsa blen 149
debug2: input_userauth_pk_ok: fp <snip>
debug3: sign_and_send_pubkey
debug1: Authentication succeeded (publickey).

I captured the full trace for a Gnome login using the good key and the bad key and did a diff:
$ diff good.txt bad.txt 
35,36c35,36
< debug1: Checking blacklist file /usr/share/ssh/blacklist.RSA-1024
< debug1: Checking blacklist file /etc/ssh/blacklist.RSA-1024
---
> debug1: Checking blacklist file /usr/share/ssh/blacklist.RSA-1023
> debug1: Checking blacklist file /etc/ssh/blacklist.RSA-1023
75,76c75,76
< debug2: dh_gen_key: priv key bits set: 123/256
< debug2: bits set: 506/1024
---
> debug2: dh_gen_key: priv key bits set: 116/256
> debug2: bits set: 518/1024
85c85
< debug2: bits set: 485/1024
---
> debug2: bits set: 525/1024
96c96
< debug2: key: /home/user/.ssh/id_rsa (<snip>)
---
> debug2: key: /home/user/.ssh/id_rsa (<snip>)
123,124c123,124
< debug1: Server accepts key: pkalg ssh-rsa blen 149
< debug2: input_userauth_pk_ok: fp ed:<snip>
---
> debug1: Server accepts key: pkalg ssh-rsa blen 148
> debug2: input_userauth_pk_ok: fp ed:<snip>
126c126,133
< debug1: Authentication succeeded (publickey).
---
> debug1: Authentications that can continue: publickey,gssapi-with-mic