That's not good... or right, obviously. Can you send us (or PM if you'd not like it to be public) a link to your site? Never seen or heard of that issue, but Facebook updated their permission requirements on July 1st, so it's possible there's some wonkiness (technical term) going on.
Some other questions off the top of my head:
When a user clicks the FB Connect button and the first permissions dialog come up, what permissions is it asking for (usually nothing, email, and/or wall posting)
Do you have the "Require Email Permissions" radio button selected in the back-end?
Was your FB application just created, or was it created before July 1st
Thanks!