I had to do this many times for different reasons and this is what I do:
This query will show you the increment id only for entity_type_code = order
SELECT * FROM eav_entity_store join eav_entity_type ON eav_entity_type.entity_type_id = eav_entity_store.entity_type_id
WHERE eav_entity_type.entity_type_code='order';
Once you located the rows you would like to update you can change them like this:
UPDATE eav_entity_store
INNER JOIN eav_entity_type ON eav_entity_type.entity_type_id = eav_entity_store.entity_type_id
SET eav_entity_store.increment_prefix='X'
WHERE eav_entity_type.entity_type_code='order' and eav_entity_store.eav_entity_store_id = {row_id_here};
Notice that the value for increment_last_id already contains the increment_prefix, so I usually removed the old increment_prefix from increment_last_id so the new orders increment id looks good.
If you have quotes with a reserved increment_order_id then is possible that you will still see orders with the old increment_id. Once you start generating new quotes after the update all should be fine.
Usually in my development environment I just set all the quotes to is_active = 0 after updating the increment_id just to have a fresh start.
For more details check here: http://www.warpconduit.net/2012/04/18/how-to-change-the-order-increment-id-and-prefix-in-magento/