Your Workflow Rule seems to be correct at first glance. Are there any tasks directly under the project?
However, I came up with a more concise way of doing this:
1) Evaluation criteria: IsChanged($C_Billed) || IsTriggeredBy("New")
2) Action 1: New Variable of type Toggle set to TRUE (let's name it AllMilestonesAreOn)
3) Action 2: Update Variable AllMilestonesAreOn
Run on: $ParentProject.Children
Filter: TargetObject.EntityType = 'Milestone' && TargetObject.C_Billed = FALSE
Value = FALSE
4) Action 3: Update Field $ParentProject.C_Billed = AllMilestonesAreOn
How does it work?
1) Runs whenever $C_Billed is updated on a milestone OR when a milestone is created.
2) Defines AllMilestonesAreOn as TRUE (just in case all of them have $C_Billed turned on).
3) Checks if there are any milestones with $C_Billed turned off and updates AllMilestonesAreOn to FALSE in such case.
4) Updates the $C_Billed field on the parent project with the calculated value of AllMilestonesAreOn.
Please let me know if this helps.