I hear some people say aftermarket fans aren't as good as OEM ones. Don't know if this is true...
Now, as for you're problem, it sounds as if you probably didn't apply enough thermal paste IF you had to. If you didn't, you probably just got a crappy cooler. In that case, I'd suggest getting some good thermal paste and try to reapply it and hopfully get better cooling.