I just got bitten by this (again) and spent many hours googling:
If you use Drupal 6 Views and try to override a node-view-VIEWNAME.tpl.php template, you MUST also override the node.tpl.php template in your theme. Otherwise it won't be picked up.
Perhaps next time, Google will hit this blog entry and I'll remember...