I had a clicking noise that was driving me crazy a while ago. It would come and go and I thought for sure it was the bottom bracket. I took it apart, repacked everything and put it back together. It seemed fine then started clicking again! I was lamenting to a friend who's into BMX bikes and he said he gets a noise sometimes when he has steel threads from pedals in an aluminum crank. I greased those and have been fine ever since. I'm guessing all the suggestions about BB threads will do the trick for you just because it stopped for about 100 miles after you changed your BB, but it never hurts to have more ideas.