There are very few things that are actually useful (socially or otherwise) but don't provide economic incentive. As pointed out by others primecoin isn't really a very good example. A good application to shoot for, if there are any budding cryptographers in the audience, is a ticking timelock encryption. A set of keys known in advance, and each block solves the next key. This would let you encrypt messages into the future, where the cost to decrypt is equal to the cost of minting that many blocks.

I've seen partial schemes for this, but no complete ones that would justify implementation. If a full and workable scheme could be devised, I would bet on it replacing sha256 based proof of work, eventually.

Primecoin also ultimately had limited utility. It found the world's largest prime number thousands of times, continually beating it's own record. At some point we had more prime numbers than had mathematical utility.

My unprovable guess is that any other non-sellable problem will ultimately have the same outcome. It's interesting and useful for a bit, but when you have a billion dollars of hardware grinding nonstop for years in a row, you eventually exhaust everything interesting about the original problem and then it's back to the same waste you started with.