Difficulty of "learning" rare instances
In the classic PAC learning (i.e., classification) model, rare instances are not a problem. This is because the learner's test points are assumed to come from the same distribution as the training data. Thus, if a region of space is so sparse as to be poorly represented in the training sample, its probability of appearing during the test phase is low.

You'll need a different learning model, which explicitly looks at type-I and type-II errors, or perhaps some combined precision-recall score. Here again, I don't think there are any results indicating that a specific class of algorithms is particularly poorly suited for this task, but I could be wrong.

The closest I can think of is sensitivity to outliers --- AdaBoost is known to have this property, for example.