This paper is concerned with first-order time-dependent Hamilton-Jacobi Equations. Exploiting some ideas of Barron and Jensen, we derive lower-bound estimates for the gradient of a locally Lipschitz continuous viscosity solution $u$ of equations with a convex Hamiltonian. Using these estimates in the context of the level-set approach to front propagation, we investigate the regularity properties of the propagating front of $u$, namely $\Gamma_t = \{ x \in \R^n : u(x,t)=0 \}$ for $t \geq 0$. We show that, contrary to the smooth case, such estimates do not guarantee, in general, any expected regularity for $\Gamma_t$ even if $u$ is semiconcave.