As shown in Richard Palais' answer, the radius $\epsilon$ of the larger tubular neighborhood can be much smaller than $1/K$.
On the other hand, at least for smooth embeddings of $\mathbb{S}^1$, the best uniform radius $\epsilon$ is also never larger that $1/K$. So in this sense yours is a necessary condition (with weak inequality though).
Consider a simple closed curve in, say, a Hilbert space $H$, with a $C^2$ arc-length parametrization $\gamma:\mathbb{S}^1\to H$. Thus, $1/K=\inf_s |\ddot \gamma(s)| $.
Let $r > 1 / K $. So there is $s _0 $ such that $ r > |\ddot\gamma (s_0) |$. Consider the point $ x _ 0 \in H $ at abscissa $r$ on the normal at $\gamma (s _0 )$:
$$ x_0 : = \gamma(s_ 0) + r \frac {\ddot \gamma(s _0) } {| \ddot \gamma(s_0)|}\,.$$
Computing the second derivative of $|\gamma(s)-x_0|^2$ at $s = s_0$ we find that the distance from $x _ 0$ to $\gamma(s)$ has a strict local maximum at $s _ 0$. Thus, in particular $s_0$ is different form the global minimum, which is also a point whose normal meets $x_0$. Therefore $x_0$ belongs to at least two normal disks of radius $r$, and in conclusion $r$ is larger than the radius of any tubular nbd.
(All that with minor changes also holds for Riemann or Hilbert manifolds; and for non-closed curves too, with some care at the end-points).