We encountered the same problem this weekend when we were doing some work in our test instance. In our case, when we run the conversion on an estimate, it creates the WO which can be pulled up, reviewed, etc. There is a corresponding Sales Order Number, but when we go to look at the sales order, it isn't found. If you do another estimate and convert, the WO & Sales order numbers increment correctly.
Looking forward to some suggestions/help on this - MCMAL