"Bad request Error 400" for GMail on Firefox

For the last 2-3 days I had an unusual situation to deal with. Whenever I tried to visit my GMail account using Firefox, the response was:
Bad request
Error 400
 At first I checked with the other browsers (Chrome, Opera and Midori) I have installed on my system. All connected without reporting anything.
Then, my next guess was misbehaving addons, but as I tweeted:
Since that approach didn't helped either, I decided to remove the GMail-related cookies. I used the "Remove cookie(s) for Site" addon and it deleted 78 cookies I had for GMail.

Unfortunately, I don't know which cookie was the "bad" one, but after deleting them I was again able to reconnect without problem.