I had this same problem. However, when a generated a new password-less private key, using the following command:
ssh-keygen -b 1024 -t rsa -f id_rsa -P ""
I no longer saw the password prompt.
Additionally, ssh-add failed to add the old key, but added the new one as expected.
I generated the old key on Leopard in 2009, using what ever version of OpenSSL I had grabbed, built and installed back then (that Mac died, so I can't log in and check what I was running). Something about that key was incompatible with Lion's native SSL libraries.
I backed up my old key, so if anyone wants to suggest some checks, to identify the key's specific properties, let me what to check and I'll report back.
Another clue - I noticed that my old id_rsa.pub file had extended attributes. i.e. it's permissions flags looked like this r--------@ instead of r--------
xattr -l id_rsa.pub.old
column = 0;
line = 1;
cruft left over from TextMate. I don't know if removing it would have fixed the issue without my having to replace the key. I think it's unlikely.
In case you (future reader) are seeing the same thing, you can remove the extended attribute as follows:
xattr -d com.macromates.caret id_rsa.pub.old
You can stop TextMate from adding them by first exiting TextMate and then issuing this command:
defaults write com.macromates.textmate OakDocumentDisableFSMetaData 1