AOFO is awesome if you need to ensure your data is always backed up. That said, it does add some sort of time-penalty, especially when you have to backup up a large amount of data (our Head Office file server is over 650GB), and there are a large number of files (well over 1 000 000 for us).
Our backups take around 16.5 hours to complete, and I need to check out how to make them quicker.
That said, the speed of your tape drive, ability to use SAN SSO if it's in place, time your backup runs, running your jobs to disk first etc. can all affect the speed of backups.
Have you looked into upping the speed of of your backup device by increasing the buffer? Leaving off files like *.mp3; *.wav etc from your selection list by putting in an exclusion?