I was having the same issue, thought I solved it by clearing my cookies, but the problem came back.
When the problem came back I was going to delete cookies, which i did anyway(this did not solve the problem this time), but then I realized my future customers may not like this option, as people don't like to have to put in much effort when making a purchase.
anyway, before I go on a rant about how this could be killing people's conversions... I'll tell you a simple thing I did that may or may not help.
I simply turned the requirement off, hit save & stay, tested the cart, then went back to my BO tab, re-saved the customization's as required & tested the cart again, and voila! it actually worked!
I'll have to test it again down the line because I'm not sure this is a true fix, but my thinking is that there is a bug occurring when I added some combinations to my products, jacking up the customization code or something, though I honestly don't know, all I do know is that it worked... for now.
hope that helps