>>> import re
>>> compiled = re.compile(b"a(\w)")
>>> s = b"aa"
>>> s = compiled.sub(b"a\\1", s)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File ".../lib/python3.1/re.py", line 303, in filter
    return sre_parse.expand_template(template, match)
  File ".../lib/python3.1/sre_parse.py", line 810, in expand_template
    return sep.join(literals)
TypeError: sequence item 0: expected bytes, str found

traced culprit to sre_parse.py <line 711> (where literal is always str):

...
def parse_template(source, pattern):
    # parse 're' replacement string into list of literals and
    # group references
    s = Tokenizer(source)
    sget = s.get
    p = []
    a = p.append
    def literal(literal, p=p, pappend=a):
        if p and p[-1][0] is LITERAL:
            p[-1] = LITERAL, p[-1][1] + literal
        else:
            pappend((LITERAL, literal))
...

a possible hack-around is <line 717>:

...
    a = p.append
    def literal(literal, p=p, pappend=a):
        if isinstance(source, (bytes, bytearray)): # hack
            literal = literal.encode()             # hack str->bytes
        if p and p[-1][0] is LITERAL:
...

Here is a patch.

The patch looks OK.

Fixed in r78729 (py3k) and r78730 (release31-maint). I also added a test for callbacks.