Conclusion

SELinux is not really hard to configure. It is just a lot of work and the current software development process does not really help here as we have seen. According to the book by Bill Mccarty SELinus also has many more concepts (capabilities, Network object protection etc.) which are not yet implemented everywhere.

Bill Mccarty's book btw. is recommended reading if you want to get started with SELinux. It does a good job to explain the concepts and I especially liked the chapters where a sample policy was developed. You will have to read it a couple of times though because SELinux is simply quite large and complex.

Does SELinux improve security? In a way yes: Domains certainly restrict program behavior. The question is: will ordinary desktop PCs use it one day? And here I doubt that the usability in SELinux is good enough to deal with average users. So I believe it will be used in special environments (firewalls, tcb machines etc.) but it wont show up as a solution for the desktop.