The issue in this case is that the order's state needs to be reset.
I had a similar issue where the invoice was deleted, but I could not create a new invoice.
I used this code on a test.php
page to successfully reset the order's status manually. It does delete all invoices in the process just in case there is anything left over.
$order_id = 97;
$order = Mage::getModel("sales/order")->loadbyIncrementId($order_id);
$invoices = $order->getInvoiceCollection();
foreach ($invoices as $invoice){
$invoice->delete();
}
$order->setState(Mage_Sales_Model_Order::STATE_NEW, true)->save();