Installed package information could be collected and then any packages not found in the repositories could be optionally stored. If non-rep packages the user could be warned and prompted to store or not as well as a list of them printed out. Also, any configuration files that are setup during install. This would make reinstallation much smoother as after a fresh install all packages previously installed could be easily restored. Also, any configuration files that are setup during install.
At this point, the users Home folder could be saved with all multimedia files or large files being optionally backed up. This can be dealt with by a simple prompt for the user once and then store in a configuration for optionally changing later. This would then need to have a list of extensions that you want excluded and a size limit for files.
Lastly, you can have a complete backup for a specified folder optionally (this looks as it is already being looked at).
These things would take care of fresh installation all they way to bringing you back with your previous configuration as well as have the option of restoring multimedia.
These backups could be divided into 4 types.
Core System (installed packages & system config)
User Profile and Documents (excludes certain files)
User Multimedia
Specified Folder (Complete backup)
Each of which could be stored seperately. This being in just different files in a single folder or on seperate medium all together (differant HDDs or even burned seperately or together on a CD/DVD).
Each should be able to be modified once the information is backed up so that they changed. This way you can have one base backup and optionally a define number of incremental backups afterwards. The base and first incremental backup should be able to be combined easily when another incremental backup is made and the other incremental backups shifted back.
Some of this has already been suggested and I appologize if any of it is repeat suggestions.
Shifting back a bit the "flow" for the user could go something as follows:
1. Prompt if they would like to backup core system (programs)
Yes - Prompt if they would like to do a full backup or "slim" backup (and notify them that restoring from a "slim" backup may require an internet connection). Also, if "slim" then list non-rep packages and ask if they would like to back them up or not.
No - Continue
2. Prompt if they would like to backup their profile
Yes - Prompt if they would like to store multimedia and large files
No - Continue
3. Prompt if they would like to backup any additional files
Yes - present with folder/file selection window
No - Continue
4. Ask where/how they would like to store backup data
5. Ask if they would like to save the settings and schedule backups regularly
Yes - Create a profile for these settings and cron job as well as setup a default incremental setting
No - Continue
6. Backup data based on information collected
As it seems there is already something in the works looking at:
https://wiki.ubuntu.com/FoundationsTeam/Specs/Backup