Я у себя делаю так (поскольку общее количество объектов сверху заранее неизвестно):
1. есть функция initGame (все названия - условные), которая порождает все объекты на сцене
2. у каждого объекта есть собственный метод remove, который чистит его внутри (удаляет все вложенные объекты и слушателей).
3. есть функция resetGame, которая аккуратно удаляет все объекты со сцены, перед удалением каждого вызывает его remove.
По уму, конечно, хорошо бы это делать на событиях, чтобы быть уверенным, что сам объект удалится только после того, его метод remove отработал полностью, но работает и так.
Кстати, если код будет немного другой, то первый объект не удалится - помешает слушатель.
Код AS3:
var a:Sprite = new Sprite(); // 1-й объект
a.addEventListener(MouseEvent.CLICK,clickHandler);
a = new Sprite(); // 2-й объект