Version 9 has Combinatorica as well. No need to go back to an older version of Mathematica.
This, by the way, is one good reason not to change things that are in the Mathematica distribution itself, but rather put them in in one of the folders that I describe in my notebook above. Then you will never overwrite something that is in Mathematica itself. You can then always choose to load the alternative package that is in on of those folders by pointing to it directly.