This message was doing my head in, below is what fixed it for me.
I reinstalled a fresh copy of macOS and all was good, until I re-installed a plugin I use in chrome called 'Videostream'... which I personally barely use anymore. As soon as it installed, notification centre alerted me that private relay was not working due to incompatible system settings..
I did a bunch of digging and found that Videostream adds a port entry to macOS' packet firewall (pf).. which, for reasons unknown breaks iCloud private relay. The below steps fixed it for me but YMMV.. (you may not have Videostream, but perhaps another app is breaking it in your instance).
open terminal, and assuming you're in an admin account:
sudo nano /etc/pf.conf
Remove lines:
# Added by Videostream service"
pass in proto tcp to port { 5557, 5556}
Ctrl+x , save yes.
Then,
curl http://127.0.0.1:5557/terminate &>/dev/null
curl http://127.0.0.1:5556/terminate &>/dev/null
sudo pfctl -f /etc/pf.conf
About 30 seconds later, notification centre alerted me IP masking with private relay was running again.
If you find any rule entries in /etc/pf.conf that don't match the default macOS ones, then you MAY have an app that's the culprit. The default values are as below.
scrub-anchor "com.apple/*"
nat-anchor "com.apple/*"
rdr-anchor "com.apple/*"
dummynet-anchor "com.apple/*"
anchor "com.apple/*"
load anchor "com.apple" from "/etc/pf.anchors/com.apple"
Bare in mind if there is a service you're dependent on that added an entry, the above steps might not be suitable for your particular use. Good luck