We investigate the oscillation spectrum of rotating Newtonian neutron stars endowed with purely toroidal magnetic fields, using a time-evolution code to evolve linear perturbations in the Cowling approximation. The background star is generated by numerically solving the magnetohydrodynamics equilibrium equations and may be non-spherical by virtue of both rotation and magnetic effects; hence, our perturbations and background are fully consistent. Whilst the background field is purely toroidal, the perturbed field is mixed poloidal-toroidal. From Fourier analysis of the perturbations, we are able to identify a number of magnetically restored Alfven (or a) modes. We show that in a rotating star pure inertial and a-modes are replaced by hybrid magneto-inertial modes, which reduce to a-modes in the non-rotating limit and inertial modes in the non-magnetic limit. We show that the r-mode instability is suppressed by magnetic fields in sufficiently slowly rotating stars. In addition, we determine magnetic frequency shifts in the f-mode. We discuss the astrophysical relevance of our results, in particular for magnetar oscillations.