Side note: Windows requires that args be quoted with ", not ', to work properly, at least with these args.

Main note: the patched test adds a space to the separator, but that is not enough to account for the difference.

c:\Programs\Python32>python -m timeit -s "seq=[bytes([i]*1000) for i in range(256)]" "b''.join(seq)"
10000 loops, best of 3: 31.7 usec per loop

c:\Programs\Python32>python -m timeit -s "seq=[bytes([i]*1000) for i in range(256)]" "b' '.join(seq)"
10000 loops, best of 3: 34.1 usec per loop

The behavior change is wrong and test_bytes.py seems to need augmentation. It begins with "XXX This is a mess. [...]".

class BaseBytesTest(unittest.TestCase):
    def test_join(self)
tests b''.join([]) but as far as I can tell, not b'something'.join([]), the failing case found by Serhiy.
It end with "        # XXX more...".