• "Clear the Cache": Tools > Options > Advanced > Network > Offline Storage (Cache): "Clear Now"
• "Remove the Cookies" from sites causing problems: Tools > Options > Privacy > Cookies: "Show Cookies"

If clearing the cookies doesn't help then it is possible that the file cookies.sqlite that stores the cookies is corrupted.
Rename (or delete) cookies.sqlite and cookies.txt, if they exist, in the Profile Folder in case cookies.sqlite got corrupted.

It might be that you are logged in with HTTP authentication (either basic or digest). This authentication is arranged by the browser, so you would have seen a pop-up dialog asking for a user name and password while logging in. It seems that these are cached by the browser and it requires you to restart the browser to log out...

http://en.wikipedia.org/wiki/Basic_access_authentication

http://www.tolaris.com/2009/09/08/logging-out-of-http-auth-with-firefox/

Because I found that having to restart the browser quite annoying I stumbled on this question and also on the HTTP Logout add-on that allows you to log out without restarting your browser. Not many sites use HTTP Authentication, but you might give it a try.

https://addons.mozilla.org/en-US/firefox/addon/http-logout/