Too many possibilities...
First regarding thermal paste, take a look at this link: http://innovationcoo...nstructions.htm (Doesn't matter if you use their paste, but shows you the impact of different application methods).
As long as the cooler is getting coverage/pressure, the stock cooler should suffice (but there are much better alternatives)... I can't comment on the Scythe cooler you have listed since it doesn't mention LGA1155, but most of them work so long as there is a universal adapter to make it work. You do need sufficient pressure at the contact point, so yes it has to be "tight" otherwise you are essentially running without a cooler.
Assuming cooler is making appropriate contact/thermal paste is okay, then disable any fan controls in the BIOS (there should be a setting that forces the PWM fan to run at full speed). Make sure you case is routing air as intended by the manufacturer (fan direction etc.).
Beyond that (assuming you don't have some crazy ambient temperatures) the 3770K runs hot to begin with, and standard BIOS settings are not always optimal (even if you are not overclocking). I had a i7-920 that ran 10-15C hotter with "stock" settings then it did overclocked to 3.8Ghz (from 2.66)... go figure. For the newer generation Intel processors, the biggest adjustments seem to come from the appropriate mix of under-volting + overclocking.
Anyway, just running out and buying a new cooler may leave you right where you started... the temperature difference between quality aftermarket coolers isn't huge, so you could end up wasting money and still have the same problem.