Phase Diagram of the Strongly Correlated Kane-Mele-Hubbard Model