Is the correlation energy of a system always negative?
The answer to this question rests on the fact that Hartree-Fock is a variational method.
A variational method is one where you supply a guess wavefunction ($|\Psi\rangle$) with some parameter(s) ($\alpha$) and then use those parameter(s) to minimize the energy. Doing this, you are guaranteed that your resulting energy is an upper bound to the exact ground state energy.
$$
E_{\text{exact}} \leq \frac{\langle\Psi_{\alpha}|\hat{H}|\Psi_{\alpha}\rangle}{\langle\Psi_{\alpha}|\Psi_{\alpha}\rangle}
$$ 

So, if we are talking about the exact correlation energy (such as one given by full CI) then the answer is that the correlation energy must always be negative. This is  because Hartree-Fock always provides an upper bound to the exact ground state energy. However, if we use a non-variational method to approximate the correlation energy (such as coupled cluster) then we could find cases where we calculate a positive correlation energy, but this is distinct from the exact correlation energy. 

(For an authoritative description of this in the context of quantum chemistry with examples and practice problems, I recommend the first chapter of Szabo and Ostlund's Modern Quantum Chemistry)