I guess all of you having this problem use baseayout-2/openrc with parallel service start. Try if rc_parallel="NO" in /etc/rc.conf fixes the problem. I had a similar problem with sshd [1] which disappeared after disabling parallel start.
[1] http://bugs.gentoo.org/show_bug.cgi?id=292843 -- Daniel Pielmeier