i speculate that with dating paradigms, women fear:

1) safety 2) stalking 3) hurting a guys feelings

men fear

1) rejection 2) stigma of "resorting" to a dating site 3) not having to face a girl he's not interested in

so, if you can solve these things you've got something.

i think an iphone/gphone app with faces you can flip through (here are some guys/girls in your area) would be neat. really simple interface. also, i'd let anyone browse, no signup, but if they want to date, they have to sign up and get verified. or something like that.

i agree about the other comment about verified identities. you might want to drop a postcard in the mail with a code and have them enter the code online to verify they're real. that would help remove the safety and stalking factor for women.