There are a couple things that I can think of that would help reduce your backup window and help with capacity.
You could look into LTO-3 or LTO-4. Capacity is 400 gig native for LTO-3 and 800 gig native for LTO-4. Throughputs are about 80 megs a second for LTO-3 and about 160 megs a second for LTO-4. You'd be looking at far fewer tapes and far higher throughputs. Tandberg Data/Exabyte (since you have a relationship with them already) has a number of autoloaders and library that have that technology integrated.
If you decide to go with the disk based option, look at
Backup Exec System Recovery (BESR). It looks like a really cool app and it might save you a lot of time with backups.