It's way too early in the lifecycle of the game to consider a character broken. Hilde's BS wasn't immediately obvious in SCIV, VC wasn't found until later in SCIII, etc. Conversely, we never had such early access to frame data before, either. If top players are doing frame data and play testing the game and have already found obvious balance issues, this might need to be considered.
That being said, he IS a CaS and by the simplest interpretation of the rules he needs to be banned. This may upset a few players and make a few others ponder the legitimacy of the ban, but oh well. We need to look out for the best interest of the community as a whole, not just the potential influx of Tekken players that may join in after seeing yet another Mishima show up in the Soul Calibur world.
As far as making the decision now, I personally believe it is a bit hasty to have it banned right out of the gate. I propose a soft-ban on the character set, but it would be difficult to implement across all of the community and all TO's in the country. While I believe that many regions will come to a final decision in the coming weeks/months and we should likely follow suit to the overall decision, I have to stand against the idea of allowing EVO to be the deciding factor. As someone else already pointed out, EVO never seems to consider Calibur to be an important franchise, and consequently it has always been something of a "shelf-item" on the roster.
