GNU sed, 65

Comments not included in score:

:                        # Define unnamed label
y/aiueo/iueoa/           # Rotate vowels
/a/y/kstnhmyr/stnhmyrw/  # If at end of row, rotate consonants
s/^a/ka/                 # If at end of 1st row, prefix a "k"
/[yw][ie]\|wu/b          # If one of the invalid values, jump back to label and redo

Oy, this is beginning to look a lot like @Martin's Retina answer (but longer, of course).