Is it correct to say a quantum particle is in both "states" at the same time?

Yes, it is wrong to say they coexist. It is better to say that the quantum state is in a combination of both of the eigenstates. I think it conveys a similar meaning to a layperson whilst also being more technically correct.

Quantum states are linear combinations of the eigenstates of the observable. They're vectors, and they exist in a vector space and do vector things like adding and dot-producting (actually they exist in an inner product space to make the braket mean something but that's by-the-by).

You would never say that a 2D vector like $\vec{r} = \frac{1}{\sqrt{2}}\left(\mathbf{x} + \mathbf{y}\right)$ is pointing in the '$\mathbf{x}$' direction and the '$\mathbf{y}$' at the same time. You would say that the vector is a combination of the '$\mathbf{x}$' and '$\mathbf{y}$' directions. Depending on how you look at the vector, you might project it onto $x$-axis or the $y$-axis. This corresponds precisely to projection operators in quantum mechanics (things like $|0\rangle\langle0|$).