The expected phenomenology of non-interacting topological band insulators (TBI) is now largely theoretically understood. However, the fate of TBIs in the presence of interactions remains an active area of research with novel, interaction-driven topological states possible, as well as new exotic magnetic states. In this work we study the magnetic phases of an exchange Hamiltonian arising in the strong interaction limit of a Hubbard model on the honeycomb lattice whose non-interacting limit is a two-dimensional TBI recently proposed for the layered heavy transition metal oxide compound, (Li,Na)$_2$IrO$_3$. By a combination of analytical methods and exact diagonalization studies on finite size clusters, we map out the magnetic phase diagram of the model. We find that strong spin-orbit coupling can lead to a phase transition from an antiferromagnetic Neel state to a spiral or stripy ordered state. We also discuss the conditions under which a quantum spin liquid may appear in our model, and we compare our results with the different but related Kitaev-Heisenberg-$J_2$-$J_3$ model which has recently been studied in a similar context.