Disk Utility: Incorrect number of file hard links
I took the laptop to Apple service centre. They ran few diagnosis and it turns out the hard disk was fine. One of those test results said that the hard disk is corrupted, and it needs to be formatted and repartitioned. So they formatted the HDD and reinstalled the OS. That seems to have fixed it.