The most-likely cause is that the "cookiepath" parameter is not set correctly in the Bugzilla configuration. You can change this (if you're a Bugzilla administrator) from the editparams.cgi page via the web.
The value of the cookiepath parameter should be the actual directory containing your Bugzilla installation, as seen by the end-user's web browser. Leading and trailing slashes are mandatory. You can also set the cookiepath to any directory which is a parent of the Bugzilla directory (such as '/', the root directory). But you can't put something that isn't at least a partial match or it won't work. What you're actually doing is restricting the end-user's browser to sending the cookies back only to that directory.
How do you know if you want your specific Bugzilla directory or the whole site?
If you have only one Bugzilla running on the server, and you don't mind having other applications on the same server with it being able to see the cookies (you might be doing this on purpose if you have other things on your site that share authentication with Bugzilla), then you'll want to have the cookiepath set to "/", or to a sufficiently-high enough directory that all of the involved apps can see the cookies.
Example B-1. Examples of urlbase/cookiepath pairs for sharing login cookies
urlbase is http://bugzilla.mozilla.org/
cookiepath is /
urlbase is http://tools.mysite.tld/bugzilla/
but you have http://tools.mysite.tld/someotherapp/ which shares
authentication with your Bugzilla
cookiepath is /
On the other hand, if you have more than one Bugzilla running on the server (some people do - we do on landfill) then you need to have the cookiepath restricted enough so that the different Bugzillas don't confuse their cookies with one another.
Example B-2. Examples of urlbase/cookiepath pairs to restrict the login cookie
urlbase is http://landfill.bugzilla.org/bugzilla-tip/
cookiepath is /bugzilla-tip/
urlbase is http://landfill.bugzilla.org/bugzilla-2.16-branch/
cookiepath is /bugzilla-2.16-branch/
If you had cookiepath set to "/" at any point in the past and need to set it to something more restrictive (i.e. "/bugzilla/"), you can safely do this without requiring users to delete their Bugzilla-related cookies in their browser (this is true starting with Bugzilla 2.18 and Bugzilla 2.16.5).