Personally, I wouldn't do an Exchange store backup and mailbox backup in the same job. The store backup is much much faster, and is the one you need in case of disaster recovery. (as you know, also flushes the logs) Get it done and safe each night, first.
If you have a small enviroment, no auto-loader, and all the data fits on one tape, you can still do both. Just create two jobs. Have the first job overwrite the tape, do the stores, and not eject the tape. Have the second job follow at a later time, and append to the tape. - gives you more flexibility in job options.
As for AOFO with mailbox backup - no experience here. The std. help file has sections for both AOFO and the Exchange agent, and addresses using the two together for mailbox level backup.
In any case, be sure to check out the Exchange Agent section of the help file; refer particularly to the document "Backing Up Mailboxes and Public Folders" - it has good tips on option settings, space saving on selections, AND which system level mailboxes to always exclude from your backup.
Cheers