Given your data sets, perhaps the following will help:

use strict;
use warnings;

my $treeFile = pop;
my %taxonomy = map { /(\S+)\s+(.+)/; $1 => $2 } <>;

push @ARGV, $treeFile;

while ( my $line = <> ) {
    $line =~ s/\b$_\b/$taxonomy{$_}/g for keys %taxonomy;
    print $line;
}

Usage: perl script.pl taxonomyFile phylogeneticTreeFile [>outFile]

The last, optional parameter will direct output to a file.

First, the tree file name is poped off (the implicit) @ARGV, and saved for later. Then the taxonomy file is read into a hash, where the identifiers becomes the keys and the taxonomy strings become the values. Next the tree file is read a line at a time, and for each line, there's a global replacement in that line of any identifier key with its associated value. Finally, the line's printed.

You could use any of the phyloinformatics toolkits available. A possible approach using Python and the ETE toolkit would look like this:

    from string import strip
    from ete2 import Tree

    # load taxonomy table (assuming that the two idname and taxonomy
    # columns are tab delimited) as python dictionary
    name2tax = dict([map(strip, line.split("\t")) for line in open("taxonomyTable.tab")])

    # loads your tree
    t = Tree("myTreeFile.nw")
    print t
    #     /-JN178341
    #----|
    #     \-GQ898616

    # replace leaf names
    for leaf in t.iter_leaves():
      leaf.name = name2tax[leaf.name]

    # check that everything is ok
    print t
    t.show()
    #     /-Bacteria;__Verrucomicrobia;__OPB35_soil_group;__o;__f;__g
    #----|
    #     \-Bacteria;__Firmicutes;__Clostridia;__Clostridiales;__Ruminococcaceae;    

    # export newick (note that you may need to replace some spacial characters from node names (i.e. ";")
    print t.write(outfile="newTree.nw")