We report on a new experiment that tests for a violation of Lorentz invariance (LI), by searching for a dependence of atomic transition frequencies on the orientation of the spin of the involved states (Hughes-Drever type experiment). The atomic frequencies are measured using a laser cooled 133Cs atomic fountain clock, operating on a particular combination of Zeeman substates. We analyze the results within the framework of the Lorentz violating standard model extension (SME), where our experiment is sensitive to a largely unexplored region of the SME parameter space, corresponding to first measurements of four proton parameters and improvements by 11 and 13 orders of magnitude on the determination of four others. In spite of the attained uncertainties, and of having extended the search into a new region of the SME, we still find no indication of LI violation.