To somewhat answer your question...
There was a project at Disney called "Wild Life" that had been on and off the boards for years. I even think Katzenberg was well aware of this before he left (or maybe even after).
The idea, as I remember, was a tale of animals at the New York public zoo who broke out of their cages and got up to all sorts of fairly lewd and crude behavior (there might have been the far off island slant in there too).
It was apparently shuttered due to Roy Disney's continued insistence that it was a dirty film and would dilute the Disney brand out of existence.
Flash forward a couple of years and Disney strikes deals with Vanguard and Core Digital to produce animated features in the event Pixar finally walked. Projects were banded about and I suspect this came up as a potential feature, with the sex and violence toned waaaaaaaaay down and farmed out to Core.
By sheer coinkidink, JK had also put a "Wild Life" type film into production, probably guessing that Disney would revive its Central Park zoo idea at somepoint and he, as usual, wanted to be the first to visit that theme. So, natch, we got Madagascar!
Now, this is all rumors, conjecture and piecing puzzles together that could have added up to zilch, but the animated world is big enough to contain a whole bunch of possibilities...
