It's quite the PITA for a site with a slew of linked products (and categories) to painfully go through those products to reset their master_categories_id to reflect the to-be-on-sale category's.
I never knew of this restriction...changing master_category ids would destroy my shop setup...I even disabled it in Store Manager.
Sounds like a bug to me. If a product is on sale, it's on sale irrespective of it's category location.