Consider a situation in which the US government realises that primecoin's output is crucial to further quantum computer research. They pump 100s of billions into mining primecoin. Now, 99.9999% of hashpower and full nodes belong to the US government - an entity whose only interest in primecoin is as a minor return on some work to reduce costs.

In this case, every assumption of trustlessness and censorship resistance has gone out the window.

A consensus algorithm using proof of useful work will become a market of miners for whom the mining rewards and thus the integrity of the network are merely a secondary concern.