I sat in on a lecture given by one of the physicists who got the Large Hadron Super Collider built in upstate NY. It was on quark-gluon plasma, which existed for the first 100,000 years after the Big Bang (assuming our models are correct, huge assumption). After 100,000 years the universe cooled enough for protons, neutrons, and electrons to form. There is only so much energy in the universe, so bringing it all together into an infinitely small space would result in infinite temperature.
Regarding the first comment on the coldest temperature, yes by definition the "coldest" something can get is absolute zero. As correctly mentioned, there is no such thing as ?cold?, only a lack of heat. To achieve absolute zero, 0K (don't use degrees with Kelvin, scientists don't) requires a complete lack of both heat and entropy which is basically disorder. Therefore, a material at 0K would have no atomic motion and be in a perfect crystalline state. This, however, violates the Heisenberg uncertainty principle which states that one cannot know both the position and velocity of an object simultaneously. We have gotten down to 10^-9 K in labs with lasers. This creates an interesting sixth state of matter called a Bose-Einstein condensate (the other five being solid, liquid, gas, plasma, and filaments).