Avi,
No, you won't have to hard reset....at least it doesn't appear you will need to
Is your inbox syncing with the original machine? What it sounds like has happened is your backup restored your emails but they are now "orphaned" so what I'd need to know is if you have indeed enabled inbox sync within activesync and that all your other emails are synching ok.