I actually posted on this discussion thread back in 2007 with statistics showing that the phrase "all of a sudden" clearly dominates in the number of hits on Google compared to "all of the sudden", but a resounding 3:1 ratio.

Checking back four years later, a Google search reveals:

"All of the sudden" - 47 million hits
"All of a sudden" - 20.4 million hits
"All the sudden" - 7 million hits

Within the short period of just a few years, it appears (based on this one data point) common usage of the phrase has decisively switched to the other side! That does not answer the question of whether one version is "correct" or not, but it certainly shows usage of "all of the sudden" is widespread...and trending towards dominant. It would be interesting if anyone did some studies on colloquial phrases, similar to how Rick Aschmann did some really interesting studies and maps on American English Dialects (look it up, it's worth checking out).

As for me, I have always used "all of the sudden" for all my 40 years in various states; whenever I hear "all of a sudden", it sounds extremely odd, similar to whenever I hear someone speak a double-negative (e.g. "I don't have no money"). Just the way I've always heard and spoke the phrase since I was a wee lad.