I've seen this a few times, the status change on a Sales Order is not a triggering update. What I've done previously has been to have one workflow on the Item Fulfillment which, via an Action Script, sets a hidden flag on the Sales Order, and then another workflow on the Sales Order which is triggered by that flag being set, which then does whatever is needed.