Hmmm, I'm not sure. But i think it has something to do with your edges orientation being messed up during modeling.

This has happened to me before. I simple did a "Cleanup" operation, and that seemed to fix the problem.

This could also be bad normals. Perhaps the normals on one of your faces in facing the opposite direction to the other, thus when the bridge operation is performed it creating the face to conform to the direction in which the faces are facing....... if this makes any scenes.

To check if the Normals are your Problem, simple do the following.... In your View Port go to: Shading>> Back face Culling. This will make the backs of your faces transparent.
Now if you can see that one of the faces your trying to perform the Bride operation on is transparent. Simple select the face and goto: Normals>> Reverse Normals. Then try the operation again.

Failing that, you could try the "Append to polygon tool" under your "Edit Mesh". Simple click on one edge and then the next..... instant face.

Other than what I've suggested i can't think of anything else at the moment. Though I'm sure some of the other members will chime in with their opinions.

-Mayaniac