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!