I don't know how to fix the general garbage collection problem, but the specific problem related to nested DO occurs (as has been already noted) because TinyScheme adds gensyms to the oblist.

Really, the gensyms would be better implemented as uninterned symbols, which is a straightforward change.  But failing that, there is a temporary workaround, which makes use of a bug in TinyScheme's force and delay to create an uninterned symbol.

Redefine gensym via

(define (gensym . sym)
  (let ((name (delay (if (null? sym) 'GENSYM (car sym)))))
    (force name)
    name))

Properties:

(gensym) => GENSYM (a symbol that PRINTS that way) on every call, but
(eq? (gensym) 'GENSYM) => #f
(eq? (gensym) (gensym)) => #f
(eq? (string->symbol (symbol->string (gensym))) 'GENSYM) => #t.

To make it easier to read macro-expanded code containing gensyms, it is helpful to give them meaningful names, via (gensym 'LOOP), for example.

[The bug in force is that (force name) returns an ordinary symbol such as 'GENSYM, but the contents of the symbol cell are then simply copied to the cell associated with name.  This is a different cell from the one containing the ordinary symbol 'GENSYM, so it is not eq? to it.  It is not in the oblist, so it can be garbage collected when it is no longer needed.]

Hope the workaround helps!
Mike G