commerce_order_status_update() doesn't update the order status After the order is paid in full (or not checkout is complete if there is no payment required and I ever get that working) I need to do a bunch of processing to set up the product the user has just bought. Only once that is done can I say the order is complete and I thought this would do it 

commerce_order_status_update($order, 'completed');


But it doesn't change the order status. They are always left as Pending.

How do I programmatically change an order status from pending to completed?
It sounds to me like you're updating the order to completed before the checkout completion rule fires that updates the order to pending. You can confirm this by looking in your revision log for the order in question.

If I were you, I'd just add a condition to that default checkout completion rule to not update the order status if it is already completed.