General class of examples: almost any combinatorial problem ever
Yes! Combinatorics problems are a perfect example of this. Trying to work out the probability of being dealt a particular hand in poker can be very difficult (for certain hands) until you correctly formulate the question- at which point the calculations are trivial : )
I think bentarm was offering "Combinatorics problems" as an example of the opposite of the phenomenon you describe. In particular the Four Colour Theorem is easy to formulate but hard to solve, and (as far as I know) the solution doesn't involve a reformulation.
Another monthly installment of the rationality quotes thread. The usual rules apply: