+1 for the simple approach, and deferring the mutual recursion support - it's desirable to keep traceback printing simple in order to minimise the chance for failures during the display process.

In addition to the C implementation of traceback printing, the standard library's traceback module would also need updating.

Regarding the ambiguity of "Previous message", I'd suggest using "Previous line" instead - that way it's accurate regardless of whether people read it as "previous line of the traceback" or "previous line of quoted source code".