Multiclass Classification with large number of categories
You might have more luck with a Naive Bayes Classifier.  It can handle a large number of target classes, and is relatively fast to train, since you largely just calculate a bunch of univariate stats to plug into at prediction time.  It won't capture fancy interactions as much as a random forest though, so if you are concerned about "they only buy shoelaces if they bought shoes but NOT shoeshine" vs "they often buy shoelaces if they've bought shoes" then it may disappoint.  You may also want to incorporate a time component, but I'm not sure what you're doing.  

https://en.wikipedia.org/wiki/Association_rule_learning may also be relevant.