What might cause the unexpected workflow state changes after executing a rule?
Option 1

Rules is great, but sometimes also tough to debug if things don't work as you'd expect. There are typically 2 ways of debugging, as further detailed below.

Rules Evaluation Log

Within the Rules settings, experiment a bit with the debugging facilities that come with the rules module. At least have a look at the "Rules Evaluation Log" (to check that the Rules logic being executed, actually matches what you expect that logic to be).

Rules Action to display a value (using devel)

You may also want to (temporary) enable the Devel module, so that you can (temporary) add a Rules Action like "Display a value".

Obviously, make sure that there are no Rules Conditions that would prevent the rules Action(s) from being executed (if needed temporary remove such Rules Conditions).

More info

For way more details about these 2 variations, move on to Rules debugging, as explained in the answer to "How can I display the value of a variable inside a condition?".

Option 2

Try to consolidate your 2 rules in a single rule, by using the Conditional Rules module. This module allows you to use Rules Conditions within Rules Actions. So in your case if you can think of an appropriate Rules Event that fits both cases, you simply use the Rules Conditions and Rules Actions within such consolidated single rule, whereas you use Conditional Rules to trigger either (not both!) of your Rules Actions.