Well, we got to play last night, and the ECL0 critters were, in fact, overpowered.
The feats Mobility and Spring Attack almost completely off-set the penalties for being Tiny. The only thing I didn't toss at them that would have shifted the balance were grappling enemies.
The reduced carrying capacities were completely off-set by the reduced weights of basically all of their equipment. Those reduced weights also messed up the prices for special material items. A Darkwood Large Shield for a Tiny charachter only costs 17 gp. Mithral full-plate only cost about 5,000 gp.
Sparky effectively had no penalty for being a Sorceror (the same would go for a Wizard). He doesn't use much gear to begin with, so the reduced carrying capacity has no effect. Being Tiny increased his AC, which was a major benefit. Finally, the addition of a climb speed and 2 racial HD shift the balance well into his favor. The other major penalty is his reduced Str, which played almost no role since mid-level spellcasters never make physical attacks anyway.
Mr. Chips was slightly effected by the decreased carrying capacity, but getting cheap mithral armor and a Darkwood shield, along with the 1/10th weight almost completely overcame this. His reduced Str did severely hamper his damage dealing capabilities, but his 3 extra HD meant that he could last long enough to make up for it. Last but not least, his human movement rate and climb speed and 2 racial feats (weapon finesse and skill finesse) more than make up for his racial penalties.
Call-me-a-chipmunk-and-die was way overpowered. His insane Dex bonus more than made up for the penalty to Str. The only real effect was that his weapons base damage was a straight 3 instead of a variable number. With spring attack and boots of Springing and Striding, he was flanking left and right, dealing a lot of damage.
All in all, I would have to say that most of the Tiny animals are between an ECL1 and ECL2. I personally would be happy to play them at an ECL2.