How can we theme menu blocks in drupal 6
You can user the theme developer module to check whether your template is called at all. It will show you what nameing conventions to use.

And just in case: You have to flush your caches to make sure new templates and theming methods are taken into account.