Érdekes kérdés.
Talán a dpkg get-selection és dpkg set-selection környékén kellene körbenézni... De verzióeltérést az nem állít vissza szerintem.
Vagy egyszerűen a synaptic napló alapján kigyűjteni a frissített/telepített alkalmazásokat, és mindkét esetben valami script-ből megoldani.
De ha neked friss telepítésre kell visszaállni akkor inkább valamilyen virtuális gép fusson a számítógépen amiben fut az Ubuntu, és a snapshotokkal elég jól el lehet játszani.