1. Close Firefox.
2. Go to your profile folder. (Profile folder - Firefox)
3. Delete the files named cookies.txt (if it exists) and cookies.sqlite
Firefox will recreate the deleted file(s) when you restart the browser.
I had the same problem. Nothing to do with "Always clear my private data..." unless you have checked "Cookies" under Settings. This worked for me:
Start -> Run (or Search box in WinVista) -> type "%APPDATA%\Mozilla\Firefox\Profiles" -> find your profile folder ("xxxxxxxx.default") -> delete file "cookies.sqlite" (and "cookies.txt"). You must close Firefox before deleting.