Using Herschel PACS and SPIRE observations of Lockman Hole-North and GOODS-N as part of the HerMES project, we explore the far-IR properties of a sample of mid-IR selected starburst dominated ultra-luminous infrared galaxies (ULIRGs) at z ~ 2. The selection of the sample is based on the detection of the stellar bump that appears in the SED of star-forming galaxies at 1.6um. We derive robust estimates of infrared luminosities (L_IR) and dust temperatures (T_d) of the population and find that while the luminosities in our sample span less than an order of magnitude (12.24< log(L_IR/Lo) < 12.94), they cover a wide range of dust temperatures (25< T_d < 62 K). Galaxies in our sample range from those that are as cold as high-z sub-millimeter galaxies (SMGs) to those that are as warm as optically faint radio galaxies (OFRGs) and local ULIRGs. Nevertheless, our sample has median T_d=42.3 K, filling the gap between SMGs and OFRGs, bridging the two populations. We demonstrate that a significant fraction of our sample would be missed from ground based (sub)mm surveys (850-1200um) showing that the latter introduce a bias towards the detection of colder sources. We conclude that Herschel} observations, confirm the existence of high-z ULIRGs warmer than SMGs, show that the mid-IR selection of high-z ULIRGs is not T_d-dependent, reveal a large dispersion in T_d of high-z ULIRGs, and provide the means to characterize the bulk of the ULIRG population, free from selection biases introduced by ground based (sub)mm surveys.