Two things I'm aware of that could be the cause of your problem. First is that the Home Page Layout must be assigned to each profile. So if you've updated it or changed the name, each profile will need to have it assigned to them. I'm presuming though that you're experienced enough to know that.
There's a similar known issue that's still in review which could be the cause of your issue, or at least points to a possible cause. See "URL No Longer Exists", the customer accesses Link of sidebar in Visualforce of package. From the article:
The customer accesses Link of sidebar in Visualforce of package, they face the error with "URL No Longer Exists".
This issue is that the link in sidebar has the package namespace.
1) Create 1 VF domain (with sidebar="true") as part of a managed package (having a package namespace);
2) Create HomePage Custom Link setting the "Content" another VF page that is not part of the manage package;
3) Access the VF page that is part of the manage package and click on the "customLink" on the left side bar.
This suggests several possibilities to me. First is that you may not have
sidebar="true" set for your managed package and that the Org has it enabled on its own. This could be what's allowing it to appear without your link or else over-riding what you've set for it's users.
Another possibility is that it's somehow related to your managed package namespace.
A third would be that it's a variant on this unresolved known issue.