I didn't think about this. A quick search and I found one population of tuna that live in the Atlantic and breeds in the Mediterranean http://www.treehugger.com/clean-technology/unraveling-the-se...

Probably they're not the only sea creatures that cross Gibraltar so this is a concern. Non a minor objection, but one among the many that would be raised. Think also about the political and military implications of a bridge from Africa to Europe.