I think we should adapt adaptive-n-factor scrypt.
Less hash power volatility, resilient to asic mining and on the long run creates a more stable coin.
Is it possible to start over?
Only start over with preserve of the coins that are all ready mined. I don't like that my electricity and hashes are wasted to put something "extra" to the coin.