I am hitting this issue. CGI::Application with a Session plugin. Every request returns the same CGISESSID to different clients. I am running the latest versions of perl and (Fast)CGI.
see https://rt.cpan.org/Ticket/Display.html?id=17541