The problem is that regular people don't understand the PGP network of trust. And even people who do understand it rarely expend the effort to make it work properly.
That's a challenge for whoever is designing the interface. It doesn't have to be that complex in terms of appearance to a casual user.
The first time they encounter a site, the software could say "You haven't visited this site before. The following people believe that it is valid: John Doe, Jane Fox, Sam Smith. Do you want to continue to it?" (Where John, Jane, and Sam are members of your social network or at least your addressbook.)
On subsequent visits it could say something (via a non-modal interaction) like "This is the same site you have visited 52 times before, most recently on Tuesday." You could have some additional validation when it looks like the user is in the process of submitting something sensitive, like an SSN or a credit-card or bank account number.
There are a lot of possibilities in that vein and I've seen a lot of proposals to handle trust like this; you don't try to turn trust into some sort of absolute metric, because that's not how trust works in the real world.
The problem with PGP's network of trust is that it tries to boil down very complex relationships into an integer value. It's not just that the interfaces suck, the concept doesn't mesh with how most users think.
