Does the prefix of an inverted unit also get inverted?
You should read $\pu{ms-1}$ as $(\pu{ms})^{-1}$ and not as $\mathrm{m}(\pu{s-1})$. Your teacher is correct.


  [...] since $\pu{Hz} = \pu{s-1}$ then $\pu{ms-1} = \pu{mHz}$


This is incorrect. 

If something happens once per hour, it happens less often than when it happens once per minute. This is because an hour is longer than a minute. In a similar manner, if something happens once per second, it happens less often than when it happens once per millisecond. This is because a second is longer than a millisecond.

So $\pu{ms-1} = \pu{kHz}$, i.e. the frequency of something happening every millisecond is larger than the frequency of something happening every second.