add_callback() can occasionally being called in a reentrant way, if a destructor triggers some non-trivial resource cleanup code.
You can find an occurrence here:
leporo/tornado-redis#59
and another here:
dask/distributed#599 (comment)

It seems a possible fix would be to temporarily disable the gc before taking the callback lock.