Brainiac definitely needs to be revamped. Of all the Superman villains I think he was hurt most in the post-Crisis DCU. I'm hoping that Johns and Busiek use the character effectively in their run (and hopefully fix his history).
The only thing that bugged me about the JLU version was he was Kryptonian, not Coluan. Otherwise, I thought he was the perfect incarnation of Brainiac: highly intelligent, coldly logical, disembodied, inhuman intellect who only used humanoid forms to interact with the world, and who could always come back from "certain destruction"...