The change in behavior is definitely caused by the changes for Issue19435. The code added there does not work correctly if there are nested directories in the "cgi-bin" directory; for one thing, the initial os.path.isdir(scriptdir) test in run_cgi is failing because the path in nextdir is missing the dir component: it's testing /path/to/test instead of /path/to/cgi-bin/test. I didn't look further. Along with a fix, there should be a test for nested directories. And decide whether to fix the regression it presumably caused in the security branches as well.
http://hg.python.org/cpython/file/d25ae22cc992/Lib/http/server.py#l1009