Are you using Admin UI for installation or API scripts?
Does the 'installed tool shed repos' page show multiple installations of the same package (with the same changesets)? If so what are the states of these?
If you check on the filesystem in the {{configured_dependency_dir}}/path/to/duplicated/package do you see any strange stuff/duplication?
How big is your Galaxy in terms of installed tools, complexity of setup and traffic?