Stock CPU fans always have PWM control so i wouldn't say it's very normal, i doubt the sensor died from a simple cleaning. At startup sometimes fans will run at full blast and then quiet down at idle. I would first check and make sure that you've installed the Heatsink properly as the sensor could be pushing the fan at that speed to try and keep an overheating chip cool.
Also see if you have any programs running behind the scenes, check task manager and look at the CPU's usage percentage at the bottom. As a program behind the scenes could be taxing the chip without your knowledge.