Why are palindrome and not-palindrome both context-free?
You make the mistake of assuming that

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$ 

while in truth

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \exists\, x \in X. \lnot P(x)$.

In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.

As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,

$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.

The complement is a nice exercise and can be found elsewhere on the site.