Given unlimited time and a perfect fitness function, could a genetic program solve any problem?
Yes.

A totally random algorithm could solve any problem given unlimited time and a perfect fitness function. All you need to do is give the GA some new random population members each generation and you're guaranteed to find the solution eventually. Even if you keep only descendants of the previous generation, setting the mutation rate and number of crossovers high enough could effectively get you random individuals.