Colder than…
My heart.
One time I was in Nevada at this casino, and started talking to the guy next to me. He was what I could describe as a senior citizen, and he was a local. Having little common ground, our talk soon turned to the weather. He briskly said that lately it had been “colder than a widow’s…pause as he realizes he’s talking to a young lady…ankle.” I had to laugh.
The thread entitled Witch Boobies had some lively discussion on this topic. 
Still haven’t found a cute female well digger for further research, though.
I knew exactly who you were talking about, without reading the chorus! That is/was OutKast (Andre 3000 in particular) in the song “ATLiens.” The fish & grits part is the chorus, and the polar bears toenails is just aline in the song. There is another line in “So Fresh N’ So Clean” that goes “cooler than Freddy Jackson sippin’ a milkshake in a snowstorm.” Great band, and two good songs. Wu-Tang clan, where’d that come from?
It’s colder than a mixture of acetone and dry ice (and that’s pretty damn cold. Of course, no one ever gets it.)
It’s colder than your girlfriend Sandra when you call her Julie.
(Cribbed, I believe, from a beer commercial. Where else are you going to find modern-day wisdom?)
I’ve always heard “colder than a polar bear’s pajamas.”, but what I usually say is “Colder than penguin snot.”
I also like…
“Colder than a tax-collector’s heart” (apologies to any tax-collectors on the Dope)
and
“Colder than an Eskimo’s outhouse.”
“And hoo BOY was it cold.”
“How cold was it?”
“It was so cold, I DIED.”
[Tom Waits again] Colder than a gut-shot bitch wolf dog with nine sucking pups dragging a No. 4 trap up a hill in the dead of a winter in a snowstorm with a mouthful of porcupine quills. [/Tom Waits again]
It was so cold…
HOW COLD WAS IT?
I’ll tell you how cold it was. it was so cold I saw a dog urinate on a fence, and he was stuck there 'til Spring!
S’cold out there!
Mine are combinations of what other have mentioned.
Colder than a witch’s titty in brass bra.
Colder than a brass toilet on the shady side of an iceberg.
I just clicked the link to the “Witch Boobies” thread, and realized I repeated my post.
[hijack] Is that the piece that starts out, “Dawn cracked hard like a bull whip and the sky turned the color of Pepto Bismol”?[/hijack]
Colder than a preacher’s dick.
Colder than a nun’s cunt.
I like that one because it’s so offensive. I’ve never used it in front of other people, though.
Wait a second! I’m a people!
How could I have forgotten:
“It’s so cold the dogs are sticking to the sidewalks.”
Thorton Wilder
Soylent Green is John_Stamos’_Left_Ear!
Very nice.