When I first got my Radeon 3850, the temp was around 39 c at idle at 50% fan speed. Now, after regularly cleaning dust from it, it averages 55 c at idle at 60% fan speed. Normally this won't bother me much, except that for some reason my computer auto shuts down when temps reach 70c, which is especially annoying while gaming. Would you guys know the solution to this problem?

I think the auto shut down is only for the CPU.

As for solving the problem... depends on how you caused the problem. Is it possible that more dust went into the HSF unit, and caused some clogging? I know this might be a little hard to get rid of...

Another solution would be to change the whole HSF unit. You'd get lower temps, but it'll cost you money, and the warranty.

would it be a good idea to buy a mini fan and have it facing the computer with the lid off?

If the problem is clogging, it wouldn't help with GPU temps, but will help with your cpu/chipset temp.

If you can, sure, try it out and see what happens.

What kind of case fans do you have set up?

I have a HP a6110n, which doesn't contain any case fans at all. I'm not sure if adding any to the back panel will be worth the time and money investment

They don't cost that much and a fan will help exhaust warm air out of th case. That will lower the overall temperature and is worth it IMO.

Would the only way to solve clogging be dismantling the entire video card fan system and cleaning it out?

bump...bump....