Classification with heavily overlapping data points of different labels
There are many approaches you could take here. Assuming data overlap in such a way that the classes are still distinguishable from a human expert—human performance is generally regarded as the performance ceiling in supervised classification tasks—you can approach this from the classifier side of the feature side.

First, I would consider the feature representation you're using for your task. A classifier is only as good as the information you give it, and there are many ways you can adjust how you're representing your input data. For example, if you're working in text classification, using a unigram representation will typically lead to different performance as compared with a bigram representation. Similarly, there may be non-linear transformations you can apply to continuous-valued data that a classifier may not pick up on its own. You should consider the domain in which your problem exists and create a set of feature generation and feature selection cross-validation experiments using a hold-out training data set.

Next I would consider what alterations you can make on the classifier end. If your data are highly skewed (i.e., one class is much more prevalent that another), it may not make sense to use an algorithm like Naïve Bayes, at least not with out some sampling approach. If your problem isn't high-dimensional, I recommend generating a graphic that will let you explore the spatial breakdown by class. There are certain overlap patterns that linear classifiers like Support Vector Machines will not be able to classify without using a kernel function, such as a Radial Basis Function.