Pure MnN and (Ga,Mn) N alloys are investigated using the ab initio generalized gradient approximation +U (GGA+U) or the hybrid-exchange density-functional (B3LYP) methods. These methods are found to predict dramatically different electronic structure, magnetic behavior, and relative stabilities compared to previous density-functional theory (DFT) calculations. A unique structural anomaly of MnN, in which local-density calculations fail to predict the experimentally observed distorted rocksalt as the ground-state structure, is resolved under the GGA+U and B3LYP formalisms. The magnetic configurations of MnN are studied and the results suggest the magnetic state of zinc-blende MnN might be complex. Epitaxial calculations are used to show that the epitaxial zinc-blende MnN can be stabilized on an InGaN substrate. The structural stability of (Ga,Mn) N alloys was examined and a crossover from the zinc-blende-stable alloy to the rocksalt-stable alloy at an Mn concentration of similar to 65% was found. The tendency for zinc-blende (Ga,Mn) N alloys to phase separate is described by an asymmetric spinodal phase diagram calculated from a mixed-basis cluster expansion. This predicts that precipitates will consist of Mn concentrations of similar to 5 and similar to 50% at typical experimental growth temperatures. Thus, pure antiferromagnetic MnN, previously thought to suppress the Curie temperature, will not be formed. The Curie temperature for the 50% phase is calculated to be T-C=354 K, indicating the possibility of high-temperature ferromagnetism in zinc-blende (Ga,Mn) N alloys due to precipitates.