I've had this issue, too. It seems like a pretty small problem, but it actually completely breaks the web of trust concept. If your network grows very much, that might become a problem, depending on usage.
The problem is that RetroShare doesn't seem to exchange key signatures. You could mess around with exporting your keys and sending them to everyone (being sure to use the "include signatures" box), but that's a huge hassle with more than a handful of people and really doesn't solve the problem. You could also use GPA and work with the GnuPG key server, which is a lot easier, but puts your public key on the net. It's called public, after all, and isn't particularly foolish as far as I know.
The best solution, I think, for the developers, would either to have a more robust key manager (including keyserver handling and such) built into RetroShare or, for real decentralization, have it act as its' own keyserver. I seriously doubt that keys.gnupg.net is going to be shut down anytime soon.