There are many many problems.
One of the biggest problem with SELinux is that it is trying to graft Mandatory Access Controls on a userland that is not designed for it.
Unix, frankly, is not designed for security. It is designed to get work done by writing a bunch of little buggy C programs that you string together in novel ways.
Security is something that was grafted on it. And it shows.
How many decades of security vulnerabilities have occurred because of a shared /tmp space? 40 years?
How do you graft access controls on a system designed with no access controls and potentially billions of combinations of programs, paths, and various other resources without breaking anything?
The answer is: You don't. You can't.
Were as you have a system designed for security, like Android, and literally hundreds of millions of fully SELinux-enabled fully locked down user-facing Linux devices are out there being used by people who haven't the faintest clue what "audit2allow" is and wouldn't understand it if you tried to explain it to them.
So it's less of an issue of "we all use software that we don't understand". SELinux is complicated enough that you can devote your life to trying to understand it and still fail to craft good rules for other people.
It's more of an issue of "Linux userland follows the basic Unix design from the 1970s which is kinda shit if your goal is security".
It is just bad design. Pure and simple. That is all there really is.
However there is a way out.
The way out is to give each process and each user their own little itty bitty special Unix environment where they can do whatever they want. And then you use strong divisions to keep them mostly unaware of each other. Use a default deny policy and only poke holes in it when required.