We need a list of backup utilities that can do the following:

- run on MS Windows (primary requirement) 
- run on Linux (supplemental requirement, optional)
- encrypt backup files before transmitting over the network
- backup to remote SFTP (Secure FTP) servers
- run automatically on schedule

Thank you.

Why dont you use psftp(http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html)
to send your backup files to a different (preferably linux) computer?
Since it is over ssh, you dont need to encrypt before sending over
network. The bonus you get is that if the files are in unencrypted
form (at the destination! after transport over network!), they will
compress better! You dont compromise over security too!

You can use a windows scheduled job to do this periodically.

If you are using psftp from windows to linux as I just mentioned, you
should first setup password-less logins. Generate an unencrypted
ssh-key(using puttygen) on the windows client, setup the remote linux
account to trust logins from this ssh key, run pageant(on windows) to
load this private key on startup, and then use psftp to transfer
files. No need to mess with passwords after that.

Thank you, but it's not quite what we want.
We are currently looking into hdup + Cygwin.