D'oh...you are 100% right. I never needed to have Remove by Restriction checked on the substitute state. I believe everything is now working the way I wanted it to. Thanks!
I personally am not in need of a battle message to let the player know a substitution did not happen, but thanks for asking.