tmutil setdestination permission denied
It was a permissions issue. I realized I couldn't even run touch somefile as my user while logged in directly on the remote machine.
Running sudo chmod -R 777 /media/timemachine and sudo chown youruser /media/timemachine may fix the issue for you.
Worth noting, I formatted /media/timemachine as ext4