It adds a whole extra step between coding a feature and deploying it. e.g. if I want to add a feature to an existing daemon to cache things in /var/cache/foo, then before deploying, I'll need to make sure the relevant SELinux policies are updated.
Also, I find SELinux gets in the way when debugging a live server. Often to solve a complex issue I'll need to ssh into a production server and inspect some sort of state or produce dumps; but if that machine has selinux installed, I end up running into it at some point or another.