I had a similar issue. I ended up using the archives.php and had a little more luck with that. It would see and use the archives.php (and the archives-video.php I created from it), but would not see taxonomy.php or taxonomy-videos.php or category.php like it should.
