BackupPC will solve all your problems (Score 3, Interesting)

BackupPC (http://backuppc.sourceforge.net/) will keep versioned backups of any network file shares including SMB and NFS. It just Does The Right Thing (TM) for using the backup storage efficiently. Throw in a web i/f for admin and file restore and it's hard to beat. I have used this to backup a small office (around 20 workstations) using a really old Compaq PC w/ an upgraded disk drive.

All you need is a cheap Linux box (Debian works well) with one or more large disks. The disks and disk controller don't need to be particularly fast either since backups happen during off hours. If you are worried about disk failure put in two drives, use software RAID, and forget about it.