Well, you guessed it right, it's the overheating, it's definitely the CPU and dust in fans has plenty to do with it.
First off, if the computer (as a whole) is under warranty, take it to wherever you bought it and ask them to clean it with an air compressor or something similar, and tell them the CPU is running too hot, suggest that they should clean the fans and apply a new layer of thermal paste. If they do all that, your work's done.
______________________________________________________________
If that's not the case, and only the components are under warranty, you'll have to do the work yourself.
Deecouple the heatsink and fan yourself and give it a thorough cleaning. If you can separate the heatsink and the fan (i.e. it's not a Zalman cooler), you can wash the heatsink with running water and let it dry off for half an hour, and you can clean the fan with a medium-hardness brush (paintbrushes with coarse hairs work).
Before reseating the heatsink+fan, pull the CPU out - just unlock the small lever on the socket and rotate it so the CPU pops out. Clean the CPU surface with a paper towel, or use Q-tips dipped in acetone, it helps remove the traces of the thermal paste. There might be some on the heatsink, so remove it too. After that, apply a thin layer of fresh thermal paste on the whole metallic CPU surface (thin enough that you can almost see the writing on the CPU - too thick and it actually worsens the heat problem), then return the CPU into the socker, rotate the lever back so it gently sinks in, recouple the heatsink and the fan on top of it.
If you've done it right, it'll definitely cool it down at least a couple of degrees.
If the problem persists, take a good look at your chassis, note where the fans are, where they're shunting air and if the air is cold or warm. Fans on the front and sides should be pushing air into the case, fans on the rear should be pulling air out of the case. If that's not the case, simply turn them around so they shunt air the other way. What you should try to achieve is so-called positive pressure, that means more air coming in than is being drawn out, because it means there's plenty of colder air to circulate.
If that still doesn't help, start looking for a better CPU cooler. If you're running on the stock one (the one that came with the CPU, as it's usually the case), it's probably not up to the task.
