Laptop going crazy

Hello, about a week ago, I was forced to do a fresh install of windows in my laptop (Toshiba Satellite L755D) due to some OS error. Since the first install, I noticed that my CPU fans were at full throttle for most of the times (even at idle instances). There were no mechanical problems with the fans themselves (i stripped them down and cleaned them completely) and I even changed the thermal Paste on the CPU... Does anyone have any clue on what the problem might be? Thanks in advance.

I went with a clean windows CD and I've already checked all the drivers, nothing seems out of normal... I will try using Ubuntu to see if it works.

I already booted Ubuntu from a Live CD (USB) and it still does the same thing (although in less frequency than with windows)... Perhaps it is an OS problem?