I raised a similar problem in Bugzilla a few versions ago, and it was fixed in a patch. Seems that something like it is back. I can't find the bug now, but it relates to the number of dots used in the cookie domain. There is no reason why sessions should require a FQDN to work, so long as the cookie domain is set correctly, and that means with the correct number of leading and trailing dots. I suspect the problem is the way the cookie domain is formed.
I hit the same problem today, when one of my users needed to use webmail for the first time since the 7.4 upgrade. "It gives me a scary error message!", and that is after getting past Firefox's dire "death to you and your unborn if you accept this certificate" warnings.
-- Jason
Edit: I've just read the bug. This line explains it all:
$conf['cookie']['domain'] = $_SERVER['SERVER_NAME'];
You cannot use the server name as the cookie domain, without *first* suffixing it with a dot:
$conf['cookie']['domain'] = $_SERVER['SERVER_NAME'] . '.';
When I last raised it, the [same] problem was with the main server-manager pages, rather than Horde.