We perform a census of the reddest, and potentially youngest, protostars in the Orion molecular clouds using data obtained with the PACS instrument onboard the Herschel Space Observatory and the LABOCA and SABOCA instruments on APEX as part of the Herschel Orion Protostar Survey (HOPS). A total of 55 new protostar candidates are detected at 70 um and 160 um that are either too faint (m24 > 7 mag) to be reliably classified as protostars or undetected in the Spitzer/MIPS 24 um band. We find that the 11 reddest protostar candidates with log (lambda F_lambda 70) / (lambda F_lambda 24) > 1.65 are free of contamination and can thus be reliably explained as protostars. The remaining 44 sources have less extreme 70/24 colors, fainter 70 um fluxes, and higher levels of contamination. Taking the previously known sample of Spitzer protostars and the new sample together, we find 18 sources that have log (lambda F_lambda 70) / (lambda F_lambda 24) > 1.65; we name these sources PACS Bright Red sources, or PBRs. Our analysis reveals that the PBRs sample is composed of Class 0 like sources characterized by very red SEDs (T_bol < 45 K) and large values of sub-millimeter fluxes (L_smm/L_bol > 0.6%). Modified black-body fits to the SEDs provide lower limits to the envelope masses of 0.2 M_sun to 2 M_sun and luminosities of 0.7 L_sun to 10 L_sun. Based on these properties, and a comparison of the SEDs with radiative transfer models of protostars, we conclude that the PBRs are most likely extreme Class 0 objects distinguished by higher than typical envelope densities and hence, high mass infall rates.