If you've got a poor stock fan installed, a new one might help. There is the possibility that it's not a problem with your fan though... though not likely, it could be that your airflow is just very poor, the thermal compound was not applied correctly or some cheap grease was used...
Answering these will help us give you a more accurate answer:
What temp is your cpu running at?
What size is the fan? it's possible you've got a junky stock 40 or 60 mm fan on there... if that's the case they have to run pretty fast to have any effect. If you're not sure of the size and you've got a digital camera, send us a picture
It's also possible that you may benefit from a new heatsink/fan unit, and a good application of arctic silver (thermal complound for good heat migration).