Justified or not, I think a project owes it to its users to change major version numbers when a major rewrite (much less a complete one) has occurred.
As perfect as your code might be, customers deserve a hint when major changes were done under the hood. Moving from 0.6 to 0.7 screams "just a few changes, some new features", not "we threw everything out and started over". This should have been made into "1.0beta", I would think.
There are other factors involved when deciding a version number than the code under the hood: API changes, new features, is it production ready, 'this is the now stable API that we'll be maintaining for a long time', etc.
Edit: for perspective, a thoughtful proposition on how to approach software versioning: http://semver.org
I agree that there are many factors. I'm just saying that some changes are important enough to trump anything else; the presence of a rewrite should decide the version all by itself.
As perfect as your code might be, customers deserve a hint when major changes were done under the hood. Moving from 0.6 to 0.7 screams "just a few changes, some new features", not "we threw everything out and started over". This should have been made into "1.0beta", I would think.