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.