using celebi is every bit as braindead as explosion, if not more.
Yet Celebi and Explosion are two quite different stories.
Explosion has a high variance of performance: It can either take out pivotal team members (e.g. Cloyster blowing up Starmie for Machamp) or completely fizzle out (e.g. hitting ghosts or Skarmory). As as bonus it often enforces suboptimal plays, whenever you try to avoid having such key members take an explosion and switch your Normal resistance/a less meaningful Pokemon into another damaging move, having erroneously expected an explosion. Add the fact that it's one-time-use and you got a strategy, which a) depends on mere guessing ("luck") rather than informed decisions ("skill") and b) enables the slightly-above-average player to beat top level players at times, and you have the perfect recipe to get people pissed off.
On the other hand Celebi has an extremely narrow set of options, which are rather supportive than actually threatening. It is very reliable at the few things it does, but will neither contribute much to the win of a battle nor end one without having done anything at all. It performance is rather stable and doesn't vary all that much. And while its use doesn't exactly put any demands on a player's skill, it doesn't "defy" skill either.
But I guess you could transfer the braindead reproach to a lot of gsc Pokemon: Snorlax (those without Belly Drum and possibly LK), Zapdos, Suicune, Umbreon (not the ML version though) and Miltank being the prime examples.
You guys have to decide: Do wish to have your set of rules a) benefit your preferred style of playing or b) create the most reasonable tiers?
For the first option, good luck with finding a consensus on what is an enjoyable metagame...
In the latter case Ho-oh and Celebi, both of which are undisputedly (Does anyone disagree??) less broken than Snorlax, shouldn't be in ubers while Snorlax is not. And for the sake of parsimony: If anything, either the two Electrics or Hidden Power as a whole should be subjected to a ban, but not the combination of a Pokemon and a move. Then again, what use are sound rules, if nobody cares to play due to a lack of enjoyment?