How to override a block generated by a module?
Have you copied block.tpl.php to your template directory as well? In Drupal 6 you need to have the base form before a more specific template will be used. For example before region-sidebar.tpl.php takes, you need region.tpl.php; before node-story.tpl.php, you need node.tpl.php. In D6 the block.tpl.php is in modules/system/.

I don't use D7, and it could've changed as David G. says.