Why can't the off-diagonal terms in density operators of pure states be always removed? The density operator for a pure state $| \psi \rangle = \sum c_i | \psi_i \rangle$ (where $\{|\psi_i\rangle\}$ is a basis) is:
$$\rho = \sum_{i,j} c_j^* c_i | \psi_i \rangle \langle \psi_j |$$
On the other hand, the basis kets themselves are pure states, and the probability of observing $| \psi_i \rangle$ is $|c_i|^2$, so we should be able to express the density operator in terms of these states (using the fact that the density operator is a sum of outer products of pure states with themselves, weighted by the probability of observing that state):
$$\rho = \sum_i |c_i|^2 \, | \psi_i \rangle \langle \psi_i | $$
Clearly these are not equivalent in general (the first has nonzero off-diagonal terms). Where have I gone wrong?
 A: 
On the other hand, the basis kets themselves are pure states, and the probability of observing $| \psi_i \rangle$ is $|c_i|^2$, so we should be able to express the density operator in terms of these states...

This statement is where your thinking went wrong. Your first density matrix describes a pure state in superposition, while your second density matrix describes a mixed state. There is a crucial difference between quantum superposition (the real state you are dealing with) and mixed state (the state that you THINK the real state is equivalent to). 
Take a simple two-state system. A superposition is of the form:
$$| \psi \rangle = c_0 | 0 \rangle +c_1 | 1 \rangle$$
You know the state FOR SURE! But when you measure it, you still get probabilistic outcomes. 
For a mixed state, you don't know what the state is! Say you have a hundred particles of which $|c_0|^2 \cdot 100$ are in the state $| 0 \rangle$ and $|c_1|^2 \cdot 100$ are in $| 1 \rangle$! Now you randomly take a particle from this collection. Sure, it is true that "the probability of observing $| 0 \rangle$ is $|c_0|^2$ and "the probability of observing $| 1 \rangle$ is $|c_1|^2$. But you are really talking about your ignorance of the system, rather than any inherent uncertainty upon measurement. The mixed state is fundamentally about classical randomness.
P.S. The off-diagonal terms signal the presence of quantum interference in the system. In case you are curious, quantum decoherence actually steers your first density matrix toward your second one when your particle is exposed to an open system. I will just provide one reference: http://vvkuz.ru/books/zurek.pdf 
Search on SE and Google for more details! 
