There are two distinct issues here:

1. I would expect that at least the given input is being classified correctly.

As mentioned, machine learning algorithms are not designed to fit the training data, rather they seek to fit unseen test data well. So trained classifiers will not necessarily classify your test data correctly.

2. The classifier outputs only True.

The fundamental reason for this are class priors: when predictions are made by Classify, the prior probabilities of each class occurring are taken into account. By default, these probabilities are estimated from the frequencies in which the classes appear in the training data. In the tennis example, there are 5 instances of True, and 3 of False, so predictions are weighted in favour of True. As a concrete example (actual class False):

In:= cl[{sunny, high, True}, "Probabilities"]
Out= <|False -> 0.486438, True -> 0.513562|>

Now specify that both classes are a priori equally likely using ClassPriors:

In:= cl[{sunny, high, True}, "Probabilities", ClassPriors -> <|True -> 0.5, False -> 0.5|>]
Out= <|False -> 0.586909, True -> 0.413091|>

The lesson: if the Classifier is not sure of which class to assign, class priors can have a large impact on the predicted class.

There are two distinct issues here:

1. I would expect that at least the given input is being classified correctly.

As mentioned, machine learning algorithms are not designed to fit the training data, rather they seek to fit unseen test data well. So trained classifiers will not necessarily classify your test data correctly.

2. The classifier outputs only True.

The fundamental reason for this are class priors: when predictions are made by Classify, the prior probabilities of each class occurring are taken into account. By default, these probabilities are estimated from the frequencies in which the classes appear in the training data. In the tennis example, there are 5 instances of True, and 3 of False, so predictions are weighted in favour of True. As a concrete example (actual class False):

In:= cl[{sunny, high, True}, "Probabilities"]
Out= <|False -> 0.486438, True -> 0.513562|>

True is predicted. Now specify that both classes are a priori equally likely using ClassPriors:

In:= cl[{sunny, high, True}, "Probabilities", ClassPriors -> <|True -> 0.5, False -> 0.5|>]
Out= <|False -> 0.586909, True -> 0.413091|>

False is now predicted!

The lesson: if the Classifier is not sure of which class to assign, class priors can have a large impact on the predicted class.