Can training examples with almost the same features but different output cause machine learning classification algorithms to perform poorly?
The answer is yes, highly similar instances in your dataset that have different target classes will cause your model to perform poorly. 

The reason for this is at the core of how all classification machine learning algorithms work. The goal of a classifier is find a function which can separate the two classes. Thus, if these two classes are very mixed then the probability of making a classification error increases and thus you will lose precision in your resulting classification. 

One method to correct this problem is to add more features to your dataset. You should try to find features which will distance the distributions of these two classes. For example if classifying cats and dogs, it would not be a good idea to use features such as: number of legs, number of eyes, etc. This will cause the classes to be indistinguishable. Try adding features such as: weight, frequency of cry, etc. This can be difficult to do often as collecting additional data is expensive. You can also try to transform your data to a new feature space. A transformation mapping your features to a different space can cause their distributions to distance themselves.