We study the co-evolution of network structure and node states in a model of multiple choice interacting agents. The system displays two transitions: recombination and fragmentation. The recombination transition distinguishes a frozen configuration composed by disconnected network components whose agents share the same state, from an active configuration with a fraction of links that are continuously being rewired. The nature of this transition is explained analytically in terms of the frustration of the rewiring mechanism leading to a divergence of the time to reach the final frozen state. The fragmentation transition, that appears between two absorbing frozen phases, is an anomalous order-disorder transition. The nature of this transition is explained by a crossover between the time scales that control the structure and state dynamics.