Re-creating cookies.sqlite may not solve the problem.
Most non third-party cookies are session cookies which are not saved in cookies.sqlite, thus they don't show in CCleaner.
If you have instructed Firefox to "Show windows and tabs from last time", session cookies are not deleted when Firefox closes, but are saved in sessionstore.js, so you still have those cookies. They can be seen in Firefox Options/Show cookies... the next time Firefox is started.
Since CCleaner isn't looking at sessionstore.js, CCleaner doesn't know the session cookies still exist.
I wouldn't call this a