big_pond,
Sorry to read about the leak. It has to be frustrating. The first thing I would do is get the original contractor out to look over the situation and make a recommendation. Depending on what he says would determine the next step.
It's only a guess but from your description, proper construction, core dam, I would first suspect the leak to be in the pond bottom itself. What is the bottom like, especially in the near vicinity of the old creek bed? It is very common around here for old creeks to go underground for portions at a time.
To fix a leak like that properly will require draining and repairing. Do you have good clay available at the site? If so, draining, packing a couple of feet over the leaking area(s) should put you back in the game.
