1) The difficulty must be adjustable so that you can make it harder or easier as computational power joins or leaves the network -- so it can't be some generically hard problem with no free parameter that affects the hardness.

2) The difficulty must be precisely predictable, so you know how much to adjust it for 1). That probably rules out NP-complete problems, where it's hard to generate random instances while ensuring you'll get one of the hard ones.

3) The problem must be capable of being arbitrarily generated from a random string, so that your work is associated with a specific ledger update (block), and so the work must have started after that node became aware of the block. This would require you to optimally "compress" the problem space so that a random string decompresses to a valid instance. But if you could compress the problem space that way, it wouldn't be hard!

Partial hash inversion (used in Bitcoin) satisfies those because:

1) You can adjust how many digits of a match are required.

2) There is no shortcut to guessing all the nonces, and each output is effectively a random number with predictable properties.

3) You can require the nonce to be prefixed by the Merkle root of the new block + previous Merkle root.

Edit: Primecoin was a good start, but it quickly exhausted all of the academically useful primes, and is unable to meet 1) while still being useful.

[1] At least, I don't know of a rigorous impossibility proof.