I looked into my system a bit further and found that other users have no problem adding links to the menus, only root can't do it. If I place mozilla.desktop into the /.kde/share/applnk/ directory then the mozilla link appears on the root K Menu. However when my mozilla.desktop is placed inside the corresponding /.kde/share/applnk/Internet directory then it doesn't show up at all.