We've all been there. The wood will be expanding/contracting slightly with moisture changes in the air. As you have screwed the top tightly to the frame these small but powerful forces are twisting the frame. Cross-bracing may only get you so far. The trick is to attach the top in such a way that a small amount of movement is permitted. The key here is to make the base frame assembly a strong unit in itself, rather than relying on the screwed-on top to add strength (due to the relatively narrow pieces used in the base, and the different grain orientations, this is less likely to twist than the wider, same-grain-oriented top). Have a look under a bought wooden table; you may see either screws coming up from the frame up into the top through oversized holes or clips/blocks attached to the underside of the top that fit into oversized grooves in the frame.
Rather than tear your nice bench to pieces, your best bet is to let it adjust to the moisture where it is going to live (assuming this is inside, where humidity changes should be less pronounced than outside), trim the legs as best you can, pack the remaining gaps between floor and legs with small pieces of card/wood, and chalk it up to experience.