I'd say try a DLT tape library & backup software of your choice. I've been away from the corporate networks for a while, but someting like Arcserve used to to the trick. I believe that ArcServe has fallen from favor, but a search for Arcserve software should bring up similar competitive products.
After the inital backups, you'll only be backing up files that are changing, so the number you should be looking at is " How much does the stored data change" during a given period of time. IF much of the data is static (archives / library / reference) then you probably need a much smaller archiving system than your total data load suggests.
A headache at first, but once the routines are established, it's not as bad as it looks. 
Good Luck
Scott
Edit: You may also want to investigate migrating to a SAN sometime in the future (again, depending on how dynamic your data is). Using a AN allows you to mirror in a partition as a RAID 0 stripe, then freeze that mirrored data set, and break the stripe, then back up the data snapshot offline. (NOTE: this is sort of an "old way" of doing SAN backups; many will provide a mechanism to back up live data ... stripe/freeze / backup works for smaller datasets and less-expensive SAN systems.)