We present new 1--1.25 micron (z and J band) Subaru/IRCS and 2 micron (K band) VLT/NaCo data for HR 8799 and a rereduction of the 3--5 micron MMT/Clio data first presented by Hinz et al. (2010). Our VLT/NaCo data yields a detection of a fourth planet at a projected separation of ~ 15 AU -- "HR 8799e". We also report new, albeit weak detections of HR 8799b at 1.03 microns and 3.3 microns. Empirical comparisons to field brown dwarfs show that at least HR 8799b and HR8799c, and possibly HR 8799d, have near-to-mid IR colors/magnitudes significantly discrepant from the L/T dwarf sequence. Standard cloud deck atmosphere models appropriate for brown dwarfs provide only (marginally) statistically meaningful fits to HR 8799b and c for unphysically small radii. Models with thicker cloud layers not present in brown dwarfs reproduce the planets' SEDs far more accurately and without the need for rescaling the planets' radii. Our preliminary modeling suggests that HR 8799b has log(g) = 4--4.5, Teff = 900K, while HR 8799c, d, and (by inference) e have log(g) = 4--4.5, Teff = 1000--1200K. Combining results from planet evolution models and new dynamical stability limits implies that the masses of HR 8799b, c, d, and e are 6--7 Mj, 7--10 Mj, 7--10 Mj and 7--10 Mj. 'Patchy" cloud prescriptions may provide even better fits to the data and may lower the estimated surface gravities and masses. Finally, contrary to some recent claims, forming the HR 8799 planets by core accretion is still plausible, although such systems are likely rare.