Brett,
Perhaps the headaches and other effects aren't caffeine related...
It appears that Aspartame (the sweetner used in Diet Coke a.k.a Nutrasweet) may not be as harmless we think it is.
Have a read:
KILLER COKE!!!
or
aspartamekills
or
Aspartame Warning
Urban legend? I don't know, I'm not one for conspiracy theories but I do like to read about them...
I guess the suggestion to go cold-turkey with just good 'ol plain water is the best suggestion
[EDIT] Ah, forgot to mention, memory loss is a side effect too, apparently...
Cas