I would venture that it is time to take the fan off the unit and blow it out real good with compressed air. I'm thinking you should be able to get it clean without removing the HSF assembly, just the fan. It probably wouldn't hurt at all to remove the entire HSF though but you will then need to clean off the old and apply fresh thermal compound to the heat sink. See where you get the easy way, if the fan speed still fluctuates then I'll recommend removal for cleaning.
Hope it helps