being that the fans in a laptop are very small and don't react well to much of anything, I would suspect that it is one of 2 things.
1. Something is in the bearings and is causing it to spin very slowly or not at all.
2. the fan is getting squished by something.
If the problem is not really the fan, then there are other options to look at. First, how is heat transferred from the CPU? Is there a heat pipe involved or is it direct cooled? Do you have a heat spreader on the VPU and the CPU? Have you done anything to the machine, or had the machine suffered any impacts (i.e. falling or something falling on it)?
How old is that machine anyway? It's pretty rare for a fan to die within the first year unless it's supper dusty, but it can happen. Also, check the Bios and see what the settings are for the fan control. If you can, set the fan to run max or whatever and set the temp allotments a bit lower.