I've installed this module and added the required code to template.php - and it seems to work fine for a "normal" menu - i.e. one that isn't primary or secondary, and which is simply added via the Blocks page.

However, I tend to use the "Menu block" module (http://drupal.org/project/menu_block) to get a bit more control. Unfortunately "Nofollow" doesn't seem to work on menus added in this way.