What you were told is a worst case scenario. With 5 labels, 20.01% is the lowest possible value that a model would need to choose one class over the other. If the probability for each of the 5 classes are almost equal then the probabilities for each would be approximately 20%. In this case, the model would be having trouble deciding which class is correct.
About the 30% comment, while it seems low, keep in mind that the model mainly uses the probability to classify the most likely label, calculating a highly accurate probability value is not the first priority.
Here is a good reference. This paper discusses a few of the problems with probability accuracy and mentions some theories on how to improve the accuracy:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.4254&rep=rep1&type=pdf
It mentions (see excerpts below) how a probability estimation in classification is a complex and difficult problem, and that some models can be very accurate at classification but poor at probability estimation, and how multi-class models are much more difficult than a binary classification model.
Excerpt 1:
"Probability estimation is known to be a quite hard problem, especially in comparison to standard classification. This comes at no surprise, noting that proper probability estimation is a sufficient but not necessary condition for proper classification: If the conditional class probabilities (1) are predicted accurately, an optimal classification can simply be made by picking the class with highest probability"
Excerpt 2:
"More generally, the Bayes decision can be taken so as to minimize any loss
in expectation. On the other hand, a correct classification can also be obtained
based on less accurate probability estimates. In fact, the classification will remain correct as long as the estimated probability is highest for the true class. Or, stated differently, an estimation error will remain ineffective unless it changes the result of the arg max operation in (2). This is also the reason for why methods like naive Bayes show competitive performance in classification despite producing relatively inaccurate probability estimates [7]."
Excerpt 3:
Methods like naive Bayes and decision trees are multi-class classifiers and
can in principle be used to produce probability estimates in this setting. In
practice, however, one often prefers to estimate probabilities in the two-class
setting, especially because estimating a single probability (of the positive class) is much simpler than estimating K − 1 probabilities simultaneously
Example with probabilities close to 1:
from sklearn import datasets
from sklearn.metrics import confusion_matrix
from sklearn.model_selection import train_test_split
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state = 0)
from sklearn.tree import DecisionTreeClassifier
dtree_model = DecisionTreeClassifier(max_depth = 2).fit(X_train, y_train)
dtree_predictions = dtree_model.predict(X_test)
print(dtree_model.predict_proba(X_test) )
[[0. 0.02564103 0.97435897]
[0. 0.91666667 0.08333333]
[1. 0. 0. ]
[0. 0.02564103 0.97435897]
...