"I don't know if this will tell you anything more than I have already said, or if it points to something really obvious."
Hi Manick ...maybe
I have looked at my Information Store logs - and there is no mention of "AOFO Initialization".
go back to Ben's earlier suggestion ...
" I would suggest splitting the job up a bit to see where it's crashing. For example, 1 job to back up file level data, 1 to backup the Information store, 1 to backup mailboxes, 1 for public folders, 1 for system state/shadow copy, etc... "
You don't need to go to that level - just take the Information Store backup(s) out of your standard selection list. Create a selection list JUST for the Information Store (and Shadow Copy Components, if you want) - but NOT mailboxes.
Then, create a job using just this new selection list. - no AOFO, etc.
This doesn't have to be your final solution, but just get this new job to START and get past that initialization error. - You don't even have to let the whole job run at this stage - you're just trying to get it to start!
let us know.