block-[region].tpl.php is not working?
My best guess is that you haven't copied across the standard block.tpl.php file into your theme. This is required (for a reason that escapes me) for overriding node and block templates.

There's a bit of a discussion about it in the comments on the link you posted.