Yes, it sure can be overheating. When cleaning, don't forget to take out and open the psu to remove the dust from inside there too.
Also remove all cards, ram modules and such so you can clean the slots they are in properly.
If this doesn't solve the problem, at least the case is clean and we have ruled out a possible cause for the problem