The solution was simple indeed. Just add this nature to the .project file of the Java utility projects:
Here goes over 8 hours of my time;). And, here are my two wishes:
1. Eclipse WTP should really give a warning if this nature is missing. Currently, there is no warning whatsoever. This is very bad, verrrrrrrrrrrry bad.
2. nick can do more meaningful work, than messing around setting like this;). (No offence, nick:)).
As far as the nature goes, you may also need this nature: