Is uncertainty and correlations actualy the same thing? In this paper on page 2 it is said that

The entropy $S(\rho_A)$ measures the amount of correlation (classical and/or quantum) between $A$ with the external world.

Now this is confusing me a little bit. If I have a quantum system described by a density operator $\rho$ I thought that $S(\rho)$ would be a measure of the uncertainty in the actual pure state of the system. In other words, this seems to be exactly like statistical physics where we have a system, we don't know the actual microscopic state, but we have some probability distribution for it.
Actually, since $\rho$ is hermitian, there is a basis such that
$$\rho=\sum_i p_i |\psi_i\rangle \langle \psi_i|,$$
and we can think that we have an ensemble of identical systems, such that if we pick one of them randomly it has probability $p_i$ of being in the state $|\psi_i\rangle$.
In that description, we have that
$$S(\rho)=-\operatorname{Tr}\rho\ln\rho=-\sum p_i \ln p_i,$$
which is the entropy of the probability distribution $\{p_i\}$ of said ensemble. 
So indeed it seems to quantify the uncertanty in the state of the system.
So why "it measures the amount of correlation with the external world"? Is correlation with the external world equivalent to uncertainty in the state? If so, how is this, because I truly fail to see it.
 A: Just to expand a little bit Bruce's answer...You can convince yourself about the properties of the Von Neumann entropy by proving two simple properties.

Let suppose to have a state $\rho$ in a $d$-dimensional Hilbert space $\mathcal{H}$ . Then:
1) $\rho$ is pure $\iff S(\rho)=0$.
2) The maximum value of $S(\rho)$ is $\log d$, and it occurs when $\rho$ is the maximally mixed state in $\mathcal{H}$.

If you take these two extreme cases, the relationship between entanglement, correlations (with external systems) and Von-Neumann entropy is evident. In the first case you have a pure state. Thus, it cannot be entangled with anything else and the entropy is zero. 
In the latter case, the state is maximally mixed. Therefore, you can take a purification $|\psi\rangle$ of $\rho$ which is maximally entangled (i.e., the purification $|\psi\rangle$ is a maximally entangled state). Indeed, the entropy is maximum.
Of course, Von Neumann entropy also quantifies the uncertainty "in the preparation of a state" (like Shannon entropy does in classical communication theory).
A: I would tend to disagree with that quote:

The entropy $S(\rho_A)$ measures the amount of correlation (classical and/or quantum) between $A$ with the external world.

I think this is only true if you assume the joint $A\otimes(\text{external world})$ to be in a pure state. In this case, as explained in steg's answer, $S(\rho_A)$ can indeed be taken as a measure of quantum entanglement between $A$ and the external world.
If you drop this assumption, then you could for example have a joint density matrix given by:
$$\rho = \rho_A \otimes \rho_E$$
(where ${}_E$ stands for the environment/external world), in which there are no correlation at all between $A$ and the external world, irrespective of what $\rho_A$ is (hence irrespective of how large $S(\rho_A)$ might be).
Letting aside that if the authors were implicitly assuming the global state to be pure, they should have made no reference to "classical correlations" (which are absent in the case of a pure joint state), that implicit assumption is in my opinion misguided. It is motivated by the idea that pure quantum states are somehow "more fundamental", with density matrices introduced as an after-thought. There exist however more satisfactory axiomatizations of quantum mechanics in which density matrices are the basic objects, recording our previous knowledge of a system. Then pure states play no special role: they are just states of "maximal knowledge", in which we happen to know as much about the system as is possible to know given quantum mechanics. But if the system in question is the entire world, I would rather expect the opposite, namely a very partial knowledge!
Now, one might think that if the system $A$ started in a pure state at some $t=t_o$, i.e. the current uncertainty in $\rho_A$ is entirely due to its interaction with a quantum and possibly noisy environment, then this uncertainty will reflect the correlations with the environment, because the two would have been generated concomitantly by the interaction. But even that seemingly reasonable statement is not true, as shown by the following example. Take $A$ to be a qubit, initially in $|0\rangle\langle 0|$, and take $E$ to be in a classical superposition of two states $\frac{1}{2} |a\rangle\langle a| + \frac{1}{2} |b\rangle\langle b|$. There exists a unitary evolution mapping $|0\rangle \otimes |a\rangle$ to $|0\rangle \otimes |a\rangle$ and $|0\rangle \otimes |b\rangle$ to $|1\rangle \otimes |a\rangle$, so that the final joint density matrix is:
$$\left(\frac{1}{2} |0\rangle\langle 0| + \frac{1}{2} |1\rangle\langle 1|\right) \otimes |a\rangle\langle a|.$$
Here, the noisy environment has managed to "contaminate" our system A, without getting correlated with it at all!
