Replace Complex Head with List

Complex is an atomic type.

AtomQ@Complex[1, 2]
(* True *)

In other words, it is a smallest unit that should be considered indivisible.

For atomic types, you cannot assume any structure. Somewhat confusingly, some of them behave as if they did have a structure in some situations. But this is by no means general.

Notice that this works:

Replace[Complex[1, 2], Complex[a_, b_] :> {a, b}]
(* {1, 2} *)

Even this works:

Replace[Complex[1, 2], head_[a_, b_] -> {head, a, b}]
(* {Complex, 1, 2} *)

So, of course, it is natural to expect this to work too:

Replace[Complex[1, 2], Complex -> List, {1}, Heads -> True]

(Notice that you would need the {1}. This was a mistake in your code, but it's really beside the main point here.)

However, this returns Complex[1,2] back.

This is what I meant when I said some atomic expressions behave as if they had a structure sometimes, but not always. For atoms, all bets are off when trying to decompose them. I suggest you stick to Re and Im, or more conveniently, ReIm.

If you try to decompose other atomic types, you will see different behaviour. Each one has its own quirks.