Well I was thinking of something along the lines of producing large prime numbers. They can be useful in cryptography. The problem is that proof of work needs a problem that takes a great deal of computational power to find a solution and very little to check the solution.
 If you are finding prime numbers then it takes a great deal of computational power to check whether it is prime. But you could turn it around into finding factors of a very large number to check whether it is prime.
 Once you have found the useful problem that needs a great deal of computational power to solve but little to check there is also the problem of whether it could be pre-mined and somebody could save up solutions and use them for a double spend so each new problem would have to be created from the last solution.
 I don't think there is any real reason why proof of work could be used on a separate problem to the blockchain as it does not necessarily have to be related. All we need is that it is in someone's best interest to use their solution to the problem to earn coins from mining rather than trying to double spend.