Now you say it… same here, something about permission denied for /usr/lib/bluetooth/bluetoothd, but when you try to run it with sudo it gives command not found.
Do a sudo chmod +x /usr/lib/bluetooth/bluetoothd and after that a systemctl start bluetooth and it runs fine.
The only weird thing is that it unsets the execute flag when you reboot and when you try to start the service it gives this message:
Warning: Unit file of bluetooth.service changed on disk, 'systemctl daemon-reload' recommended. Job for bluetooth.service failed. See 'systemctl status bluetooth.service' and 'journalctl -xn' for details.
I tried reinstalling the bluez package, which corrected the permissions again, but after a reboot again the file was changed… @sam_nazarko you know how this can be caused?