It seems not even using -S fixes the problem:

[16:25] brief:python-traceback-test% head -n 2 caller.py 
#!/usr/bin/python3 -S

[16:25] brief:python-traceback-test% ./caller.py 
Indirect child being called
Indirect child being called
Indirect child being called
^Ccaught signint in parent
Traceback (most recent call last):
  File "/usr/lib/python3.2/functools.py", line 176, in wrapper
    result = cache[key]
KeyError: (<class 'str'>, '[ \\f\\t]*(\\\\\\r?\\n[ \\f\\t]*)*(#[^\\r\\n]*)?((([0-9]+[jJ]|(([0-9]+\\.[0-9]*|\\.[0-9]+)([eE][-+]?[0-9]+)?|[0-9]+[eE][-+]?[0-9]+)[jJ])|(([0-9]+\\.[0-9]*|\\.[0-9]+)([eE][-+]?[0-9]+)?|[0-9]+[eE][-+]?[0-9]+)|(0[xX][0-9a-fA-F]+|0[bB][01]+|0[oO][0-7]+|(?:0+|[1-9][0-9]*)))|((\\*\\*=?|>>=?|<<=?|!=|//=?|->|[+\\-*/%&|^=<>]=?|~)|[][(){}]|(\\r?\\n|\\.\\.\\.|[:;.,@]))|([bB]?[rR]?\'[^\\n\'\\\\]*(?:\\\\.[^\\n\'\\\\]*)*\'|[bB]?[rR]?"[^\\n"\\\\]*(?:\\\\.[^\\n"\\\\]*)*")|\\w+)', 32)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "./__testpython", line 4, in <module>
    import site
  File "/usr/lib/python3.2/site.py", line 58, in <module>
    import traceback
  File "/usr/lib/python3.2/traceback.py", line 3, in <module>
    import linecache
  File "/usr/lib/python3.2/linecache.py", line 10, in <module>
    import tokenize
  File "/usr/lib/python3.2/tokenize.py", line 118, in <module>
    _compile, (Token, PseudoToken, Single3, Double3))
  File "/usr/lib/python3.2/tokenize.py", line 115, in _compile
    return re.compile(expr, re.UNICODE)
  File "/usr/lib/python3.2/re.py", line 206, in compile
[16:25] brief:python-traceback-test%     return _compile(pattern, flags)
  File "/usr/lib/python3.2/re.py", line 255, in _compile
    return _compile_typed(type(pattern), pattern, flags)
  File "/usr/lib/python3.2/functools.py", line 180, in wrapper
    result = user_function(*args, **kwds)
  File "/usr/lib/python3.2/re.py", line 267, in _compile_typed
    return sre_compile.compile(pattern, flags)
  File "/usr/lib/python3.2/sre_compile.py", line 495, in compile
    code = _code(p, flags)
  File "/usr/lib/python3.2/sre_compile.py", line 477, in _code
    _compile_info(code, p, flags)
  File "/usr/lib/python3.2/sre_compile.py", line 366, in _compile_info
    lo, hi = pattern.getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 163, in getwidth
    i, j = av[1].getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 153, in getwidth
    l, h = av.getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 163, in getwidth
    i, j = av[1].getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 153, in getwidth
    l, h = av.getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 163, in getwidth
    i, j = av[1].getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 153, in getwidth
    l, h = av.getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 163, in getwidth
    i, j = av[1].getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 153, in getwidth
    l, h = av.getwidth()
  File "/usr/lib/python3.2/sre_parse.py", line 147, in getwidth
    REPEATCODES = (MIN_REPEAT, MAX_REPEAT)
KeyboardInterrupt

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "./__testpython", line 26, in <module>
    if re.match("__", os.path.basename(sys.argv[0])):
NameError: name 're' is not defined