Considering the FX-8350 is out-performed in most games by a $110 Intel CPU, I would not spend much on cooling for it. As heavymetal2000 says, if you want to overclock, grab something cheap (<$30) like the 212 EVO, and wait a bit to see how things pan out. I expect Zen is not going to make much of a splash for most desktop users, but the longer you hold onto your FX, the more CPU power you'll be able to get for your dollar, as Intel generally releases their next generation of CPUs at the same price as their old ones.
What cooler did your prebuilt include?