The other natural frequency is indeed zero! Natural frequencies of zero corresponds to vibrational modes of rigid body motion. Rigid body motion is not a vibrational motion in itself, but still arises in the modal analysis of certain systems such as the one above. The reason you get a rigid body mode is because you are able to move the system as a whole, and no restoring force exists to bring the whole system back to its original location.
This system is equivalent to hooking up one of the masses to a fixed point using a spring of zero stiffness. Let's consider your system with mass $m_1$ connected to a fixed point with a spring of stiffness $K$. Upon performing modal analysis, the two natural frequencies of such a system are given by:
$$\omega=\sqrt{\frac{m_1 + m_2}{2m_1 m_2}k + \frac{K}{2m_1}\pm \sqrt{\left[\frac{m_1 + m_2}{2m_1 m_2}k + \frac{K}{2m_1}\right]^2 - \frac{Kk}{m_1 m_2}}}$$
Now, to reobtain your system, set $K=0$, and the two frequencies indeed become $0$ and $\sqrt{\frac{m_1+m_2}{m_1 m_2}k}$. So the lowest natural frequency of your system is indeed zero, but what is the physical significance of a natural frequency of zero? One way to interpret it is a vibration of infinite time period, $T=2\pi/\omega$. When the bodies move, it takes so long for them to finish their first oscillation that it never completes, i.e. the body continues moving on at constant speed. This corresponds to rigid body motion under no external forces (modal analysis for determining natural frequencies sets externally applied forces to zero anyways.)
Hope that answers your question :)
P.S. Also, note that the zero frequency result does appear alongside the non-zero result when you first calculate them:
By taking the determinant of the relevant matrix, the following equation is obtained:
$$\omega^4 - \frac{m_1 + m_2}{m_1 m_2}k\omega^2=0$$
Note that this can be rewritten as:
$$\omega^2 \left(\omega^2 - \frac{m_1 + m_2}{m_1 m_2}k\right) = 0$$
So it can be seen that $\omega^2 = 0$ if one of the two solutions. It is quite easy to miss this, as it can be prematurely cancelled out of the equation, which can only be done if $\omega^2 = 0$ is an impossible solution, which it is not.