Here's an answer, but it's not a fix.
The concrete5 dev team confirms it's a problem in 8.1 when C5 is running from a subfolder rather than the root of the web site, e.g (as described in the issue report referenced above) as http://mycompany.com/directory rather than http://mycompany.com.
So, one potential fix is to reconfigure your website to run as the top-level site in your domain.
If that's not possible, you could patch the file CookieMiddleware.php as described in the issue description (2 lines, simple fix).
Or you could wait for the next point release (8.2). No indication from the dev team when that might be.