What kind of classification should I use?
Using your input data as-is (many categorical attributes), you should start with random forests.  The levels of your features probably aren't ordinal in any sense, which would explain why multinom (a linear model) didn't work.  A decision tree (component of a random forest) won't have trouble with categorical features that aren't ordinal.

If your features are correlated (I'm guessing they are highly correlated), you might also try first reducing the dimensionality of your input dataset.  A nice way to do this is to view your categorical features as "words" and map each input sample (a word in all its forms) to a sparse vector (training a TF-IDF model).  Then, reduce the dimensionality of your sparse vectors using LSI or LDA (dense vectors).  Train a classifier (again, random forest is a good starting point) using these dense vectors as input data.