What's an appropriate algorithm for classification with categorical features?
What you have is called a classification problem with categorical features. That is, the features can be represented numerically, but the numbers have no relative meaning.

Algorithms that rely on smooth function approximation will probably not work well here. These would include classic approaches to regression, and also function approximation via a neural network. That's because the data are anything but smooth!

In contrast, classic classification algorithms like Quinlan's C4.5 decision tree learner, (implemented in the Weka Toolkit as J48, and possibly in SciKitLearn as DecisionTreeClassifier, though the documentation is less clear), are ideal for this: they actually work by splitting up numeric values into discrete categories anyway, so there's no issue at all for them. Most versions also support a way to pre-tag features as categorical, and the algorithms rely on the cross-entropy of each feature's categories, without making assumptions of smoothness.