I have lived in Ohio, then Texas, then Colorado, then California. And, as far as I can remember, I have always heard and used the phrase "All of the sudden". The phrase "all of a sudden" simply sounds "wrong" to me -- in the same way some people say "aunt" while pronouncing the "u", or say "PEE-can" instead of "peh-CAHN".

Interesting experiment -- I checked on Google, and found:

"All of a sudden" - 2.5 million hits
"All of the sudden" - 750,000 hits.
"All the sudden" - 340,000 hits.

Under Google News, there are 6900, 660, and 350 hits respectively.

And on Blogsearch, there are 350,000, 39,000 and 17,000 hits respectively.