Has anyone attempted to rewrite the bitcoin software and protocol?
I believe that is what the NXT project is attempting to do.

It is a from scratch implementation of the ideas introduced by Bitcoin et al. They use Proof-of-Stake and claim to provide "built-in support for robust features such as a decentralized peer-to-peer exchange, voting system, messaging/chat, decentralized DNS, and options for instant transactions".