The price of Tuna is set of "how expensive is it to produce a can of tuna" rather than "how many tuna are left in the ocean". In fact, the lower the production cost of tuna fishing, the higher the risk that we empty the ocean of all the tuna.
It's really a problem of the Tragedy of the commons. There is no cost of tuna in the ocean, except the cost of fishing it. So it's a commons, and it will be overexploited.
http://en.wikipedia.org/wiki/Tragedy_of_the_commons
also: be sure to understand http://en.wikipedia.org/wiki/Collapse_of_the_Atlantic_northw...
If I sell fruit but I get it by stealing it from a neighbour then I'll be able to afford to sell the fruit at a far lower cost than the cost of manufacture and still get a profit.
The problem comes when the threshold is reached and passed. That is specifically the tragedy of the commons. It's a fractal problem - i.e., even if one country fixes the issue through regulation/taxes/prohibition, another country may still overfish a shared body of water.
The "full cost" wouldn't need to be replacing each fish caught. It would be a fee/tax to ensure a sustainable fish population - this could still result a reasonable market for fish.
In the past we fished at sustainable levels because we were incapable of fishing to extinction. WWF (http://wwf.panda.org/about_our_earth/blue_planet/problems/pr...) say we're taking 2-3 times the volume of fish from the oceans as is sustainable.
http://www.thekitchn.com/use-caution-when-eating-escola-6660...
It really seems like the FDA or FTC should be able to regulate that a little bit.