Doped perovskite cobaltites (e.g., La$_{1-x}$Sr$_x$CoO$_3$) have been extensively studied for their spin-state physics, electronic inhomogeneity, and insulator-metal transitions. Ferromagnetically-interacting spin-state polarons emerge at low $x$ in the phase diagram of these compounds, eventually yielding long-range ferromagnetism. The onset of long-range ferromagnetism ($x approx 0.18$) is substantially delayed relative to polaron percolation ($x approx 0.05$), however, generating a troubling inconsistency. Here, Monte-Carlo simulations of a disordered classical spin model are used to establish that previously ignored magnetic frustration is responsible for this effect, enabling faithful reproduction of the magnetic phase diagram.