What is the difference between overfitting and "not learning" I am trying to build a Random Forests (RF) model using around 2000 observations and a number of features (can be 50 or can 1000, I still do not know which features are to be used).
One way to evaluate the learned model is by plotting true vs. predicted values from the test set. Suppose I observe the following scenario:

On the x-axis we have the true values and on the y-axis the predicted ones. On the left we have the training set and on the right the test set.
For training we can assume the $R^2$ (regression problem) to be around 0.9 while for testing it's around 0.3/0.4. Furthermore, the Mean Absolute Error (MAE) on the test set is around 0.4 while the model predicting just the mean has a MAE of around 0.6 (with values of the target variable between 0 and 5).
My question is then: how can we say whether the model is overfitting or if the chosen features are simply not enough to make the model learn some relation with the target variable? Is it the same problem but stated in a different manner?
One way to avoid observing such a huge difference between training and test sets, is by increasing, for instance, the minimum number of samples required to be at a leaf node. This would decrease the training score to 0.7 and increase the test score to 0.5. But still, what if the problem is with the selected features?
 A: This is overfitting, and should not be dealt with by manipulating just one aspect of prediction development such as leaf node size.  You have to look at all the possible tunings that can be done with RF, and these tuning parameters are critical.  But this avoids the main problem: RF may require up to 200 events (or 200 observations in the continuous Y case) per candidate feature.  So your sample size is very low for RF.  See this.
I am not clear why you don't know the number of candidate features in your problem.
However you decide to go forward, it is important to have unbiased estimates (e.g., from an independent holdout sample or using rigorous cross-validation) of both predictive discrimination (e.g., $R^2$) and absolute predictive accuracy (smooth calibration curve and scatterplot as you did).
A: Random Forest models 'overfit' by definition, however this seldom has an effect on their predictive power. When you are passing a training sample down it's corresponding random forest model, the sample will end up in the exact same terminal nodes it ended up during training. Therefore, the above left plot depicts the deviation of the sample value from the mean values of samples which share a terminal leave node with it. 
Random Forests are a form of NN model and thus the conventional definition of overfitting, i.e. performance of the model on train vs. test samples, does not really make sense, as the later will almost always be lower. 
Overfitting is generally not an issue in context of Random Forests and increasing the node size, pruning the trees, etc. might actually hurt the model, as it can increase the bias. 
Selecting meaningful model features is another topic but again, Random Forests are relatively robust against noisy features, as the uninformative ones will simply be not selected during a split. There exist many ways of feature selection (e.g. forward/backward selection based on certain variable importance measures) but those are mostly used for model interpretation purpose. 
