Inventory API and Simple Stock Levels doesn't use Workflow configurations for changing stock levels, so I think you must be using the core uc_stock module instead. With the Inventory API, stock levels are adjusted at order submission, not at order status change.

Check admin/build/modules and make sure you only have the core uc_stock enabled. Then you can use the uc_stock Workflow condition like Ryan said to specify when the stock gets decremented.