The following instructions are based on using PhpMyAdmin. If using Nexcess.net this is accessible through the Siteworx Panel
Look at the eav_entity_type.entity_type_code for the "order" record as seen here
In this example we will see the entity_type_id = 5
Go to the eav_entity_store table in the MySQL Database and edit the record with entity_type_id = 5
Enter the new next order number as seen here and hit Go
NOTE: Make sure to keep the order number 9 characters long