In this paper, we consider robust non-linear precoding for the downlink of a multiuser multiple-input single-output (MISO) communication system in the presence of imperfect channel state information (CSI). The base station (BS) is equipped with multiple transmit antennas and each user terminal is equipped with a single receive antenna. We propose two robust Tomlinson-Harashima precoder (THP) designs. The first design is based on the minimization of the total BS transmit power under constraints on the mean square error (MSE) at the individual user receivers. We show that this problem can be solved by an iterative procedure, where each iteration involves the solution of a pair of convex optimization problems that can be solved efficiently. A robust linear precoder with MSE constraints can be obtained as a special case of this robust THP. The second design is based on the minimization of a stochastic function of the sum MSE under a constraint on the total BS transmit power. We formulate this design problem as an optimization problem that can be solved by the method of alternating optimization, the application of which results in a second-order cone program that can be numerically solved efficiently. Simulation results illustrate the improvement in performance of the proposed precoders compared to other robust linear and non-linear precoders in the literature.