Motivated by recent experiments showing nonlinear elasticity of in vitro networks of the biopolymer actin cross-linked with filamin, we present an effective medium theory of flexibly cross-linked stiff polymer networks. We model such networks by randomly oriented elastic rods connected by flexible connectors to a surrounding elastic continuum, which self-consistently represents the behavior of the rest of the network. This model yields a crossover from a linear elastic regime to a highly nonlinear elastic regime that stiffens in a way quantitatively consistent with experiment.