What is the best classification technique where I have 1500 categories to predict and 100,000 observations?

Classification with many categories has actually been a fairly active research area in recent years.  See http://jmlr.org/proceedings/papers/v28/bi13.pdf for a recent paper with a decent literature survey.

Haven't really worked on anything like that but perhaps I can offer some ideas. I would start with something simple for a baseline and work from there. In theory, multinomial logistic regression seems like the right type of algorithm for this. There could be some computational issues if you have 1500 classes but I don't have enough experience with this to be able to tell for sure. An alternative would be to use a binary classifier in a one-vs-all configuration. This would work with logistic regression, linear SVM, kernel SVM, etc. With 1500 classes, you would have to compensate for the massive ratio of negative to positive samples for each class, either by resampling or weighing classes to reflect the proportions. Before setting to work on classification, I would plot a histogram of the labels to get a feeling for their proportions. If they are very uneven, many learning algorithms might fit to the most common classes and end up rubbish at predicting the rare labels. The techniques that I mentioned for one-vs-all configurations might be helpful with this problem. After exploring the basic methods, I would try to see if there is any hierarchical structure in those labels. Some of them might be clusters of similar objects, so it could be helpful to predict the cluster first and then have classifiers to distinguish between different classes within clusters. Also have a look at Google scholar and the paper that @Justin-Rising suggested. And if you publish a paper on this, please let us know :-)

Depending on the nature of your problem, you might want to treat it as information retrieval, rather than classification problem. For example, if your observations are textual, and categories are some sort of document clusters or classes, then something as simple as  bm25 might work good enough. You might want to put additional "smaller" rankers or classifiers after this step. For non-textual observations, you might be able to use simple Bayes network as described here http://arxiv.org/pdf/1304.1511.pdf

I would start by asking if the observations are separable into 1500 categories, and whether they are adequate enough for any classifier to generalize well I would recommend reading the error correcting output code approach by Dietterich and Bakiri : Solving Multiclass Learning Problems via Error-Correcting Output Codes http://arxiv.org/pdf/cs/9501101.pdf

You can define the problem as a whole optimization problem instead of naive one vs all or one vs one look and go into it.. There are many papers about this topic and some of the real applications are used for image net challenge. However it comes with some memory bloating since all the model is kept in a matrix optimized by each iteration.