It sounds like the customer did more than just replace the harddrive. Maybe they replaced the harddrive and other components. Or they replaced the harddrive and instead of installing the same version of Windows they installed another version. In any of those cases TurboActivate will see the computer as being different.
As far as deactivation goes, since the customer presumably no longer has access to the old harddrive, just deactivate them from within LimeLM (find their product key, then click "Deactivate" next to their activation on the pkey view page).
If you're using IsGenuineEx() in your app (instead of IsActivated()) then you shouldn't have any fraud problems. Meaning, if they're really installing your app on a different computer (instead of just replacing a harddrive like they said), then the old computer won't be able to user your app after X days.
Make sense?