I don't really see the relation with my problem; I am not using paludis overlay, but portage version of paludis..
m4 package can't be installed still; I can't upgrade paludis or coreutils to do that, because they depend on m4 and the vicious circle ends...