Previous theoretical studies have demonstrated that tetrahedral N-4 Should be an extraordinarily effective high energy density material. But this species has thus far resisted laboratory efforts directed to its synthesis. Ab initio electronic structure methods have been used to examine the Td N-4 and O-h N-8 nitrogen clusters, including their protonated forms. We have optimized geometries using DZP, TZ2P, and TZ2P(f,d) basis sets with the Hartree-Fock self-consistent-field (SCF) method, second-order Moller-Plesset perturbation theory (MP2), single and double excitation configuration interaction (CISD), coupled-cluster (CCSD and CCSD(T)) methods, and three DFT/Hartree-Fock hybrid (B3LYP, B3P86, BHLYP) methods. Harmonic vibrational frequencies and infrared intensities have been obtained at the SCF, MP2, B3LYP, B3P86, and BHLYP levels of theory. The vertex protonated O-h N-g and T-d N-4 structures are found to represent minima on their respective potential energy surfaces. The bond protonated T-d N-4 molecule was determined to be a transition state leading to the vertex protonated T-d N-4 isomer. The predicted proton affinities of T-d N-4 and O-h N-8 support the possibility that standard laboratory techniques for deprotonation may be used to yield these elusive high-energy density materials. The molecular properties determined at the DFT/Hartee-Fock hybrid level of theory are compared to large basis set coupled-cluster results and found to be in good agreement, even when relatively small basis sets are used for the former.