The phase structure of two-dimensional topological insulators under a sufficiently strong electron-electron interaction is investigated. The effective theory is constructed by extending the idea of the Kane-Mele model on the graphenelike honeycomb lattice, in terms of U(1) lattice gauge theory (quantum electrodynamics). We analyze the phase structure by the techniques of strong-coupling expansion of lattice gauge theory. As a result, we find that the topological phase structure of the system is modified by the electron-electron interaction. There evolves a new phase with the antiferromagnetism not parallel to the direction pointed by the spin-orbit coupling, in-between the conventional and the topological insulator phases. We also discuss the physical implication of the new phase structure found here, in analogy to the parity-broken phase in lattice quantum chromodynamics, known as the "Aoki phase."