Can mining puzzles be made socially valuable?
To be valid as a proof of work a problem needs to


be difficult to produce, and it's difficulty must scale up and down as the network speed requires. The levels of difficulty must be quite granular, bitcoin's go down to several decimal places to ensure an even blocktime.
have no central issuer, the work must be independently creatable and verifiable. No central authority should be needed to produce problems and solutions.
be quick to verify even on microprocessors, every node in the network must verify it 300,000 times over to synchronize with the blockchain today. Currently I can verify a sha256 merkle tree proof on a processor that costs a few cents in bulk;  scrypt coins are almost useless in that you need a huge amount of memory to verify the proofs. 


Nothing else can fit this bill at all. Primecoin attempted this, but it's method has removed the ability for SPV clients to operate (kilobytes of stupid number strings in the block headers), and the work it produces (certain types of prime numbers in a sequence) is merely a curiosity rather than anything usable by anybody. 

It must be a cryptographic hash. The simple fact that it is protecting the network means that it is not "useless".