I'm having a similar problem. I think it is to do with sessions and the database. If you haven't seen this:
https://www.zen-cart.com/tutorials/index.php?article=281
try it. It hasn't helped me but you might have success. I also tried the cache key fix script from dr byte:
http://www.zen-cart.com/index.php?main_page=product_contrib_info&products_id=82
but that tells me there is no problem there.
So far as I can tell the problem started after running a large sql report (with the 'sales report' module). But mine is not as consistent. Some operations my admin can handle, sometimes. Yes it is that irregular. I've found that clearing the cache / cookies etc can make the difference between any click sending me back to log in and only certain operations sending me back to log in. As an example I could look at the list of 'customers', look at different pages on the list, examine their details but if I try to rearrange them by surname I get sent back to the log in. I've tried logging in from a different machine and met the same issue. At present my session tracking is set to 'db' instead of '' for file use. Everything had been running fine for months. I've had a look at the sessions table in the database and nothing is screaming 'danger! danger!' at me but I don't know what I'm looking for.
What else can I check / look for / test?
Thanks for any illumination you can offer.
Cheerio for now,
Alan