I would guess this has to do with uneven mixing of the agar, as Karen suggested. We had the same issue once or twice and now I make sure to two things:
1. Stir immediately after coming out of the autoclave and after adding CaCl2 and dextrose.
2. Swirl aliquots after taking from water bath and before using for overlays. This is especially important if they have been sitting for some time, e.g. overnight.

Since then, we've only had one unexplained failure to set.