I noticed this a while ago.  And FWIW it's not just 3.x; I see this same behavior in 2.6.

I've whipped up a test case, attached, which runs in both Python 2 and Python 3.  The test runs "sys.interpreter -V" four times: it tries all the combinations of shell=True/False and the cmdline argument as either a list or a string.

When shell=True and cmdline is an array, Python runs as an interactive shell.  (You have to press Ctrl-D to close it; the test warns you this is happening.)
When shell=False and cmdline is a string, Python raises OSError, "[Errno 2] No such file or directory".
In the other two cases the code runs correctly, producing the version number of Python.

The test would probably be better if I used stdin=PIPE too, so you didn't have to press Ctrl-D.  But I couldn't figure out how to make it produce the interactive session stuff when I did that.  Anyway, it wouldn't be hard to make this into a proper regression test.

My two cents: I assume from the discussion that this is not fixable; that is, it's not possible to have a shell and a string, or no shell and a list.  Failing that, the right decision is what R. David discussed on 2010-02-28: ignore the shell argument passed in and infer it ourselves from whether cmdline is a list or a string.  I don't buy the security argument--since the invalid combinations of shell and cmdline mean the function doesn't work, existing callers have already made the decision whether they can live with shell=True.  We should deprecate the shell argument and update the documentation to make the behavior crystal clear.