Background for other visitors
Discord is defined as the difference between two quantities. One quantifies the total correlations between the two subsystems, and the other quantifies the classical correlations between the two subsystems. Thus the discord is non-zero only if the state has non-classical correlations. Separable states cannot have non-classical correlations (I'll show this below), but some separable states have non-zero discord (I'll show an example).
That sounds like a contradiction, which is what the question is asking about.
The resolution is that the term "non-classical correlation" is overloaded: it has two inequivalent meanings in the preceding paragraph. I'll answer the question by explaining how the two meanings of "non-classical correlation" differ from each other and how they relate to discord and separability.
Inequivalent meanings of "non-classical correlation"
Let $\rho$ denote the state, represented as a density matrix.
Definition 1: A state $\rho$ has non-classical correlations if no local hidden variables model can account for all expectation values of the form $\text{trace}(\rho'\, X\otimes Y)$ where $X,Y$ are observables on the first and second subsystem, respectively, and where $\rho'$ is obtained from $\rho$ using single-subsystem measurements and post-selection. (The last concession is needed in order to expose the hidden nonlocality of some mixed entangled states.)
Definition 2: A state $\rho$ has non-classical correlations if it cannot be written as a mixture of pure states, each of which is a product state, using a fixed orthogonal basis for each subsystem.
These two definitions are not equivalent: the condition in definition 1 implies the condition in definition 2, but not conversely. Separability relates to definition 1. Discord relates to definition 2.
Separability and definition 1
Consider a given factorization of the Hilbert space, ${\cal H}={\cal H}_A\otimes{\cal H}_B$. A mixed state $\rho$ is called separable whenever it can be written as a weighted sum of separable pure states,
$$
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\rho = \sum_{s} w_s |s\ra\,\la s|
\tag{1a}
$$
with
$$
|s\ra = |s_A\ra\otimes |s_B\ra.
\tag{1b}
$$
The first subsystem's states $|s_A\ra$ don't have to be mutually orthogonal, nor do the second subsystem's states $|s_B\ra$.
A state of the form (1) satisfies
$$
\text{trace}(\rho\, X\otimes Y) = \sum_{s} w_s
\la s_A|X|s_A\ra\,\la s_B|Y|s_B\ra.
\tag{2}
$$
Equation (2) can be used to construct a local hidden variables model for all quantities of the form $\text{trace}(\rho\, X\otimes Y)$, so separable states don't have non-classical correlations in the sense of definition 1.
Discord and definition 2
The precise definition of discord is a little complicated. To keep this answer short(er), instead of reviewing the precise definition, I'll quote a result that relates it to definition 2.
First, some more background. A state $\rho$ is called quantum-classical (that is, quantum in the first subsystem and classical in the second subsystem) if it can be written as in (1) such that all of $B$'s states $|s_B\ra$ are mutually orthogonal. This terminology comes from the fact that classical physics can be regarded as a special case of quantum physics in which all observables commute with each other and in which the state is always an eigenstate of all of the observables. In this sense, states in classical physics are always orthogonal to each other (cf What makes a theory "Quantum"?).
Here's the result that relates discord to definition 2:
- The state $\rho$ is quantum-classical if and only if its discord $D(A|B)$ is zero.
Discord is asymmetric: generally $D(A|B)\neq D(B|A)$, corresponding to the asymmetry between quantum-classical and classical-quantum. Again, "classical" is understood here to be a special case of "quantum", so the set of quantum-classical states includes the set of classical-classical states, those for which $D(A|B)=D(B|A)=0$.
This result is stated concisely in section 3.6.4 in "Quantum correlations in composite systems under global unitary operation" (https://chaos.if.uj.edu.pl/~karol/prace/Luc18.pdf), which cites the more comprehensive review paper "Quantum discord and its allies: a review" (https://arxiv.org/abs/1703.10542).
A separable state can have non-zero discord
To prove that definitions 1 and 2 are not equivalent, here's a separable two-qubit state with non-zero discord:
$$
\rho \propto |x\ra\,\la x| + |y\ra\,\la y|
\tag{3a}
$$
with
\begin{align}
|x\ra &\propto |0\ra\otimes |0\ra
\\
|y\ra &\propto |1\ra\otimes |+\ra
\\
|+\ra &\propto |0\ra+|1\ra.
\tag{3b}
\end{align}
This is manifestly separable. To show that its discord $D(A|B)$ is non-zero, I'll use the condition reviewed in equation (5) of "Necessary and sufficient condition for non-zero quantum discord" (https://arxiv.org/abs/1004.0190), which is directly related to definition 2: a state $\rho$ has non-zero discord $D(A|B)$ if and only if there is a set of mutually orthogonal $1$-dimensional projection operators $P$ for the second subsystem such that
$$
\rho = \sum_P (1\otimes P)\rho (1\otimes P).
\tag{4}
$$
For the state (3), this condition implies the pair of conditions
\begin{align}
\sum_P P|0\ra\,\la 0|P &= |0\ra\,\la 0|
\\
\sum_P P|+\ra\,\la +|P &= |+\ra\,\la +|,
\tag{5}
\end{align}
which in turn implies that both of the states $|0\ra$ and $|+\ra$ are eigenstates of both of the $P$s (to see this, left-multiply both equations by one of the $P$s), which is impossible because $|0\ra$ and $|+\ra$ are not mutually orthogonal. This shows that the state (3) has non-zero discord, even though it is separable.
How *should* the term "non-classical correlations" be used?
Is definition 2 a good use of the term "non-classical correlations"? This is a matter of opinion, but personally I think that language is confusing.
If we prefer the langauge of definition 1, then we could describe a separable state with non-zero discord as having "classical correlations between non-classical subsystems." That seems more clear to me.
Whether or not we describe it as having "non-classical correlations," states with non-zero discord do exhibit quantum effects. The question already acknowledged this, and I'll cite an example: the paper "Quantum discord as a resource for quantum cryptography" (https://arxiv.org/abs/1309.2446) shows that non-zero discord — but not entanglement — is a necessary condition for secure quantum key distribution. (Entanglement becomes necessary if the evesdropper has access to the noise sources.) The reason is related to the no-cloning theorem: an evesdropper could clone the transmitted qubit's state if it were limited to an orthogonal set, but not if it is drawn from a non-orthogonal set.
