Disk Could Not Be Partitioned - First Aid not helping
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.