Disk Could Not Be Partitioned - First Aid not helping
Solution 1:
I had very similar problem. After contacting Apple Support and following their instructions, I've reinstalled macos (instructions here). This is not a wipeout reinstall, but do make a backup.
After the reinstall partitioning worked like a charm.