What is the simplest example of a prob whose complement does not have the same complexity?
The notion of "complex" depends entirely on your model of computation. For example, if you're using DFAs, then by just about every conceivable measure every problem has the same difficulty as its complement. On the other hand, if you're using PDAs as your model of computation, many languages can be recognized by a PDA even though their complements can't. For example, the language


  { ww | w &in; {a, b}* }


is not recognizable by any PDA, but its complement is.

In the land of NP, we don't know much about the relative difficulties of problems and their complements. It's an open problem whether the complements of any NP-complete problems are in NP.

Looking at decidability, a problem is decidable if and only if its complement is decidable. However, the same is not true of recognizability. The halting problem is recognizable, but its complement isn't.