Q:

multiple ways to do the same thing

Using multiple icons to mean the same thing. Its a pretty common UX technique to allow for users with different types of mental model to be able to navigate; some people like top menus, others icons elsewhere, etc...
However, in some of my testing we found the system that had been developed suffered from giving users too much choice. That there were too many ways to do the same thing just overwhelmed some users, they weren't sure which was right and 'real'.
I wonder, does anyone know of any rules or best practice on just where the balance lies between giving choice that helps and too much choice?

A:

Sometimes, the ability to do the same thing in multiple ways feels awkward to the user because the user cannot choose easily between the methods.
This happens when each method seems to be at the same level in the user's model of the interface. In fact not just at the same level, but if you imagine a tree-like hierarchy, then at the same node.
If you talk to users and try to get an understanding of their mental model (as opposed to the system model) you'll find that that they might chunk different actions and features together.
As a simplified example, consider a text editor. I can make selected text bold by using the Edit menu, a popup context menu, or by using Ctrl-B. Now each of these do the same thing but I'm not confused by this because in my mind I've chunked those activities in the categories of 'menu access', 'right click access' and 'keyboard shortcuts'. I can determine in my own mind that there is really one function and the other options are alternate accessors from different nodes of my mental model that do the same thing. Those nodes are not alone - there are other right click features and there are other keyboard shortcuts, which is why I'm happy to group them together separately in my model.
Now consider that I could use Ctrl-B to make the text bold or I can use Ctrl-E to Embolden it (bear with me!). They do the same thing but suddenly I have two ways to do something and their nodes live side by side in my mental model. My feeling is that two sibling items in the model should do unique things - not the same thing, and therefore I have to decide which of the siblings to use.
Obviously this is a simplification for demonstration purposes, but does show that if you design the interface in such a way that you make users group functionality so that there are no 'twins' in the mental model, then users will be less inclined to feel they have to make decisions between them.
Do this by documenting all your alternate methods - like some kind of process flow - essentially building that user's mental model. Try to group the methods along with other functionality that is 'similarly different' - i.e. where you think the user should be chunking those alternate methods together. Think about what is stopping the user from identifying that group and how you might stop the user from seeing the methods as twins rather than being found at different nodes. If necessary, prune the user process tree to clean up the model. Do all this in conjunction with data collected from user testing or feedback you have received, and of course, verify the changes with other stakeholders based on the evidence.
Summary:

understand the mental model your users are seeing
help the user to form a cleaner simpler mental model
group sibling functionality 
avoid twins in the same group (they fight)
avoid tiny groups (they don't feel like a group)

