Lots of problems.
One problem: If the work exists before it is time to solve it then people can "save up" solutions and cause short term double spends eventually regardless of how small their power is. With Bitcoin the problem is "made up" when the previous block is found.
Wouldn't they still need to devote the power to solve the problem? Perhaps you could break the problems into smaller chunks to be randomly checked out by single solvers.