I found many websites, referencing the solution at http://orwin.ca/2011/11/09/crm-2011-left-navigation-label-changes-not-visible-by-users/ - however that website (when I was looking) was not available for whatever reason.
Luckily, I found enough 'bits' of comments in peoples comments to piece together a possible solution.
This is that solution. (That worked for me!)
Create a new Security Role that will be assigned to the users you want to see the navigation modifications.
Click Settings, Administration, Security Roles
Next, Click NEW
Give the role a name
Click the Customizaton Tab and Select the option for ISV Extensions
Save this role and add it to the relevant staff members.