When working on real problems there are not likely to be any silver bullets. No technique (including GP) is likely to solve all instances of an NP-hard problem in an amount of time that grows linearly with the size of the problem. GP has proven extremely successful in a wide variety of domains (e.g., Chapter 12 ) but that doesn't mean that it will work immediately or easily in every domain, or even that it is the best tool for a specific domain.
While some of the successes in the field have been "easy", most were the result of significant effort by experienced practitioners. It is likely that for every GP approach that has successfully solved a problem, several others have failed. It is in the nature of academic publishing that one does not get to hear about failures.
So, don't expect immediate success, and don't become too discouraged by poor early results.