If you imagine this as a question and answer conversation, you get:
A: He phoned her.
B: When did he phone her?
A: Not long after his breakfast.
The two statements spoken by person A are separate and distinct statements but if they are put in the same statement, they require a comma when used in one order and no comma in the other:
1) Not long after his breakfast, he phoned her.
2) He phoned her not long after his breakfast.
You can't start with "Not long after, ..." because, without any other information, it would be impossible to know "after what".
The statement of time is "Not long after his breakfast", not just "Not long after".