Which factors make the problem of inferring the grammar difficult?
Regarding the difficulty of learning grammars, let's stick to regular ones for concreteness. These are precisely the grammars/languages recognized by Deterministic Finite-state Automata (DFAs). The source of difficulty is purely computational; the statistical aspects are quite straightforward. 

If you were able to find the smallest DFA consistent with your finite sample, simple Occam/cardinality arguments guarantee that this will generalize very well (it's the "optimal" learner in some sense). See Theorems 2 and 3 of Graepel et al.
http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf
for actual state-of-the-art bounds. 

However, finding such a small DFA is VERY hard (see Angluin, Gold, Pitt-Warmuth, etc):
http://www.sciencedirect.com/science/article/pii/S0019995878906836
http://web.mit.edu/6.863/www/spring2010/readings/gold67limit.pdf
http://dl.acm.org/citation.cfm?id=138042
[the latter even gives a hardness-of-approximation result].

But wait, it gets worse! Suppose you didn't care about a DFA and just wanted to learn the grammar in some representation (i.e., a mechanism for predicting the labels of test strings drawn from the same distribution as the training set).
If such an algorithm were to exist, and succeeded against all distributions, then it would also break RSA and related cryptographic primitives:
http://dl.acm.org/citation.cfm?id=697797