So to fix this we added the "get connected" feature. Basically it's a page after the initial login where people can open a session to all their social networks and provide all their frequent email addresses. This way they can login with any of these. This helped a lot.
The Stack Exchange network has a similar feature. Each user can associate a Facebook account, an e-mail address and password, and multiple OpenID identifiers (Google, AOL, Ubuntu, etc.) to his Stack Exchange user account. The one thing I'm surprised they don't support is Twitter login.