Number of features vs. number of samples : if small sample size is sufficient, why take large number of samples?
Bounds on the needed amount of samples are very common in PAC learning.
When you define a concept class you can compute a minimal size set of sample that will enable learning. 
However, 


More samples will allow improving accuracy
More samples will enable learning more complex concepts, that might fit your data better.
As @Emre wrote, real life data sets usually are not clean as in PAC learning. The concept class is not given to you, the data has noise and a given distribution is not guaranteed.


Showing that a classifier can be learnt with a small amount of data is great. 
It is a big advantage of the learner.
However, more data usually helps and if it helps more than expected for such a classifier, it is possible that the classifier requirements doesn't hold.