If it is not access rights issue, then may be the problem is that Add-ons UI module is not deployed or is not initialized properly.
Please check that modulesbin directory in the site root contains EPiServer.Packaging and EPiServer.Packaging assemblies.
Also please verify that EPiServer.Packaging and EPiServer.Packaging.UI modules are deployed in the site VPP folder, like C:\EPiServer\VPP\MySite\Modules
Application pool must have read and write/modify access rights for the VPP folder, subfolder and files.
In addition you can enable debug logging for the site, restart and see if there is any useful information in the log.
I have seen the thread: http://world.episerver.com/Modules/Forum/Pages/Thread.aspx?id=70099 which describes the issues as the logged in user not having PackagingAdmins rights in the EPiServerFramework.config but I have checked this and my user is part a member of the WebAdmins role that was created.
I am running v 7.1 Patch 3
It had been working but somewhere along the way it stopped showing up.
If I browse directly to /EPiServer/AddOns I get a 404.
What else controls whether that link is shown?