Both are correct.
I believe the difference is due to that fact that CelciusCelsius isn't the actual unit - the unit is called a "degree". Since we have two different ways of measuring temperature in units called "degrees", we distinguish between them with the name of the creator of the system - "Celcius""Celsius" or "Fahrenheit". These are proper nouns, and so are capitalised. The units themselves (which are usually named after people), aren't capitalised.
So, if we were talking about Lord Kelvin, who gave his name to the kelvin unit of temperature, we capitalise his name, but with the unit itself we don't (as seen in this very sentence).
This gets a bit confusing, appearing to contradict the "a name not a unit" explanation, when people say "60 Fahrenheit" or "40 Celcius"Celsius", etc - really this is shorthand for "60 degrees Fahrenheit" or "40 degrees Celcius"Celsius".
EDIT - on a side note, you will sometime see people use "290 degrees Kelvin" - I believe that this is acceptable, even though it's not the official unit. If you do use it like this, capitalize "Kelvin". So, you can say
290 kelvin
or
290 degrees Kelvin
Stick to the former, though, since it's the standard.