Bitcoin does not solve this issue, a blockchain does. That's what the guys at Ethereum for example are trying to achieve: vanilla blockchain, build anything on top.
Counterparty could solve this, on Bitcoin's blockchain [1]:
> Counterparty works by storing extra data in regular Bitcoin transactions, which makes every Counterparty transaction a Bitcoin transaction, albeit a very small one. When Counterparty transactions are broadcast to the Bitcoin network they are verified by Bitcoin miners and saved in the Bitcoin blockchain to make a secure, verifiable record.
> Counterparty works by storing extra data in regular Bitcoin transactions, which makes every Counterparty transaction a Bitcoin transaction, albeit a very small one. When Counterparty transactions are broadcast to the Bitcoin network they are verified by Bitcoin miners and saved in the Bitcoin blockchain to make a secure, verifiable record.
[1] http://counterparty.io/