I know it is an old thread but I'm in the same situation, the order status has been changed, but the emails were not sent.
I found solution to the Alex original code:
$objOrder = new Order(1); //order with id=1
$history = new OrderHistory();
$history->id_order = (int)$objOrder->id;
$history->changeIdOrderState(3, (int)($objOrder->id)); //order status=3
just add this at the end:
$history->addWithemail(true);
in my PS version 1.4.10 it works perfectly