First, let me give you my general configuration:
- I am using SAMBA to share my homes directories to my Windows clients. The main/live data store is on the Linux box.
- I have configured a backup share on one of the Windows boxes that will be mounted on the Linux box, and used for backup of the data store.
- I plan to make incremental backups weekly, and full backups monthly, of the home directories.
- Total data size will easily be in the hundreds of gigs.

I would like to know what backup/restore utility(s) would be best for this mixed OS configuration?
I would prefer that the chosen utility has sync capabilities for faster backups, as well as verify.

You may find interesting reading here:
http://www.linux-backup.net/App/