The reason that we can have $\vec{E} = 0$ at the center of the cube but $\vec{\nabla} \cdot \vec{E} \neq 0$ is the same reason that we can have a function $f(x)$ that vanishes at $x_0$ but for which $f'(x_0) \neq 0$. The two pieces of information are not incompatible.
If you recall, the divergence of $\vec{E}$ is defined as $$ \vec{\nabla} \cdot \vec{E} = \frac{\partial E_x}{\partial x} + \frac{\partial E_y}{\partial y} + \frac{\partial E_z}{\partial z}. $$ If we look at the first term here, it corresponds to the rate of change of $E_x$ with respect to $x$ near the center of the cube. If we imagine starting at the center of the cube and moving away from it along the $x$-axis, we will see that $E_x$ increases along this line; after all, near the center, we would expect the electric field to be small but to point away from the center at a point close to the center. So it should seem plausible (at least) that $\partial E_x/\partial x \neq 0$. Similar arguments hold for the $y$- and $z$-directions.
Finally, note that the same "paradox" happens for a solid sphere of charge: we have $\vec{E} = 0$ and $\vec{\nabla} \cdot \vec{E} \neq 0$ at its center as well. The resolution there is exactly the same.