How to test this:

# atomic host status
...
# ps axZ|grep -i rpm-ostre
system_u:system_r:install_t:s0   12134 ?        Ssl    0:00 /usr/libexec/rpm-ostreed

Verify you see install_t there.  Next, you can test rebasing to 7.3: https://mojo.redhat.com/docs/DOC-967002

Applying the fixed packages via 'ostree admin unlock' and then relabeling the binary was successful.

-bash-4.2# ostree admin unlock 
Development mode enabled.  A writable overlayfs is now mounted on /usr.
All changes there will be discarded on reboot.
-bash-4.2# rpm -Uhv selinux-policy-3.13.1-63.atomic.el7.7.noarch.rpm selinux-policy-targeted-3.13.1-63.atomic.el7.7.no
arch.rpm 
Preparing...                          ################################# [100%]
Updating / installing...
   1:selinux-policy-3.13.1-63.atomic.e################################# [ 25%]
   2:selinux-policy-targeted-3.13.1-63################################# [ 50%]
Cleaning up / removing...
   3:selinux-policy-targeted-3.13.1-60################################# [ 75%]
   4:selinux-policy-3.13.1-60.el7_2.7 ################################# [100%]
-bash-4.2# restorecon -v /usr/libexec/rpm-ostreed 
restorecon reset /usr/libexec/rpm-ostreed context system_u:object_r:bin_t:s0->system_u:object_r:install_exec_t:s0
-bash-4.2# systemctl restart rpm-ostreed.service 
-bash-4.2# ls -lZ /usr/libexec/rpm-ostreed
-rwxr-xr-x. root root system_u:object_r:install_exec_t:s0 /usr/libexec/rpm-ostreed
-bash-4.2# ps axZ | grep rpm-ostree
system_u:system_r:install_t:s0   12633 ?        Ssl    0:00 /usr/libexec/rpm-ostreed
unconfined_u:unconfined_r:unconfined_t:s0-s0:c0.c1023 12641 pts/0 S+   0:00 grep --color=auto rpm-ostree
-bash-4.2# rpm-ostree rebase rhelah-autobuild:rhel-atomic-host/7.3/x86_64/autobrew/buildmaster                        

1322 metadata, 7789 content objects fetched; 326059 KiB transferred in 67 seconds                                     
Copying /etc changes: 40 modified, 4 removed, 99 added
Transaction complete; bootconfig swap: yes deployment count change: 1
...

Since the problem described in this bug report should be
resolved in a recent advisory, it has been closed with a
resolution of ERRATA.

For information on the advisory, and where to find the updated
files, follow the link below.

If the solution does not work for you, open a new bug report.

https://access.redhat.com/errata/RHBA-2016:1831