Too much thermal glue would have a negative effect, you are supposed to use as little as possible to ensure the maximum efficiency (the thermal-contact glue is just supposed to SEAL the processor to the heatsink). Also, CPU fans are VERY touchy. You are only supposed to use compressed air to clean them.
I've worked on quite a bit of computers and have had fans go like that before after a cleaning (they weren't necessarily going faster, but definitely made noise). The only time I ever had a fan go faster was when I broke the thermal-paste seal. It also made some extra noise though.
If the fan is making excess noise, the problem is probably with the fan itself and you should replace it.