These noises are the worst. There are many threads on clunk-chasing around, but basically you need to eliminate all of the easy sources: seat, seatpost binder, bottle cages, cable housing slap, stem, handlebar, front derailleur, wheel not centered, QR skewer loose. From there, you move on to the tougher ones: pedals, crankarms, cassette / rear hub, bottom bracket. And I'm probably forgetting a lot. Lube everything up and tighten up and see what you get.
That said, if you had to have the BB tightened, then my money would be on that, especially if it solved the noise problem to begin with. A new one is $25 plus installation.