Dealing with "trouble maker" samples I have a pretty large data set (~300 cases with ~40 continuous attributes, binary labeled) which I used to create several alternative predictive models. To do this, the set was divided to training and validation subsets (~60:40%, respectively).
I have noticed that there are several samples (both in the training and the validation subsets) that are being misclassified by all or most of the alternative models that I test.
I suspect that there is something special about these "trouble making" samples. What are the general guidelines for discovering the possible reasons behind the misbehavior of the models on specific samples?
Update 1. I'm using logistic regression for this task. The parameter selection is done by exhaustively searching combinations of up to 4 predictors with 10-fold cross validation. It is worth mentioning that the p-values that is calculated by the model for the misclassified samples are usually very different from the default classification threshold of 0.5. In other words, not only is the model wrong about those cases, it is also very confident about itself.
Update 2 - what I have already done.
I agree that insights from the study domain are crucial, but to date we have failed to discover anything significant. Also, I tried to remove the "bad" samples from the training set, and keeping the validation set and the parameter selection algorithm untouched. This led to better performance on the training set (naturally), but also improved significantly the performance on the validation set. Is this an indication that the "bad" samples were actually "bad"?
 A: I think this will require domain expertise. If I were you, I would spend time examining these samples and their provenance, to figure out what (if anything) is wrong with them. If the samples were collected by a colleague working in some application domain, they may be able to help you with this.
Sometimes, samples can indeed be 'bad'. For example, they could be mislabelled, collected under different circumstances from the rest, collected using off-calibration equipment, or there may be many other reasons why they're outliers. However, you shouldn't just say "these are probably bad" and delete them; much better to identify what's wrong with them so that you can verify that they're bad and justify their deletion.
One reason for caution is that they might not actually be bad, just drawn from part of your sample space that's not well represented in the data. In that case, you shouldn't toss them out, you should (if possible) collect more like them.
Another reason is that the samples at the extremities of a concept are the ones that may be hardest to classify correctly, but if they are not actually bad and you remove them, you just end up with new samples at the extremities. To take an artificial example, suppose you are classifying samples as Hot/NotHot, and everything above 50 degrees should be hot. Samples at 49.9 degrees and 50.1 degrees are quite similar even though they're different sides of your decision boundary, so they're just hard to classify and they're not outliers that should be tossed. Also, if you remove them, you may find that two new samples (49.8 and 50.2 degrees) that were previously being classified correctly are now getting misclassified.
One final point: when you say that samples in the training set are generally being misclassified, do you mean under a cross-validation scheme or literally that when you test on the training data that they are misclassified? If the latter, it could be that the classification methods you are using are not able to capture the data variance sufficiently well.
Hope this helps a little ... 
A: I think you are suffering from the presence of outliers in your design matrix. 
The remedy is to detect them using a multivariate robust estimator of location/scale (just as you can use the median to detect outliers in an univariate setting but you can't use the mean because the mean itself is sensitive to the presence of outliers). High quality estimators are already present in the R-base tool (through MASS).
I advise you to read the following (non technical) summary introduction to multivariate robust method:
P. J. Rousseeuw and K. van Driessen (1999) A fast algorithm for
     the minimum covariance determinant estimator. Technometrics
     41, 212-223.
There are many good implementation in R, one i recommend particularly is covMcd() in package robustbase (better than the MASS implementation because it includes the small sample correction factor).
A typical use would be:
x<-mydata #your 300 by 40 matrix of **design variables**
out<-covMcd(x)
ind.out<-which(out$mcd.wt==0)

Now, ind.out contains the indexes of the observations flagged as outliers. You should exclude them from your sample and re-run your classification procedure on the 'decontaminated' sample. 
I think it will stabilize your results, solve your problem. Let us know :)
EDIT: As  pointed out by Chl (in the comments, below). It could be advisable, in your case, to supplement the hard rejection rule used in the code above by a graphical method (an implementation of which can be found in the R package mvoutlier). This is wholly consistent with the approach proposed in my answer, in fact it is well explained (and illustrated) in the paper i cite above. Therefore, i will just point out two arguments in its favor that may be particularly relevant to your case (assuming that you indeed have an outlier problem and that these can be found by the mcd):


*

*Provides a visually strong illustration of the problem with outliers as each observations is associated with a measure of its influence on the resulting estimates (observations with outsized influence then stand out).

*The approach i proposed applies a strong rejection rule: in a nutshell, any observation whose influence over the final estimates is larger than some threshold is considered an outlier. The graphical approach might help you save some observation, by trying to recover those observations whose influence over the estimator is beyond the threshold but only by a small amount. It is important in the context of your model because 300 observations in a 40 dimensional space is rather sparse already.

A: Addressing the issue mentioned under Update 2.  You are dealing with outliers.  Those outliers have a significant impact on your Logistic Regression coefficients.  By removing them, you found that your models performed better on the validation set.   
Does it mean that the outliers are "bad"?  No.  It means that they are influential.  There are several measures of statistical distances to confirm how far away and influential such outliers are.  Those include Cook's D and DFFITS. 
Having identified the trouble makers, you are struggling with whether to keep them in or not.  Ultimately, this may be a qualitative judgment rather than a statistical question.  Here are a couple of investigative questions that may be helpful in making this qualitative decision: 
1) First, are the outliers truly bad due to poor measurements?
2) Is it more important for your models to be correct in the tails where outliers reside or be more accurate in the vast majority of the cases?  
