Using Herschel PACS and SPIRE observations as part of the HerMES, we explore the far-IR properties of a sample of mid-IR selected starburst dominated ultra-luminous infrared galaxies (ULIRGs) at z ~ 2. We derive robust estimates of infrared luminosities (L_IR) and dust temperatures (Td) of the population and find that 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. We also demonstrate that a significant fraction of our sample would be missed from ground based (sub)mm surveys (850-1200{mu}m) showing that the latter introduce a bias towards the detection of colder sources. Similarly, based on PACS data as part of the PEP project, we construct for the first time the full average SED of a sub-sample of infrared luminous Lyman break galaxies at z ~ 3, and find them to have higher T_d when compared to that of SMGs with comparable L_IR. We conclude that high-z ULIRGs span a wide range of dust temperatures, larger than that seen in local ULIRGs, and that Herschel data provide the means to characterize the bulk of the ULIRG population, free from selection biases introduced by ground based (sub)mm surveys.