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.
Not sure if it is possible, but maybe if there is a major update to the client that it automatically changes the mining function starting from block X