Shot in the dark here, but what kind of clay did you use/discover? Could it be something like the Crucible is associated with one clay type and not another? I was able to build a Crucible with Metalworking, Masonry, Ball Clay and Bricks - no metal discovered at all yet.
Trying to think what else I did making mine. I think I built my ore smelter first, have you completed one of those yet? Are you looking in the right section of the Build menu (Tools->Crucible, not Construction)?
I can confirm I have never made coal either, so that should not be it.