Height transitions go from top down, rather than from bottom up in D3

If you inspect the bar elements, you can see that d3 bars are drawn from a the required height to the y position. So you should try as shown below.

svg.selectAll(".bar")
  .data(data)
  .enter().append("rect")
  .attr("class", "bar")
  .attr("x", function(d) {
    return x(d.letter);
  })
  .attr("width", x.rangeBand())
  .attr("height", function(d) {
    return height - y(d.frequency);
  })
  .attr("y", height)
  .transition()
  .duration(500)
  .attr("y", function(d) {
    return y(d.frequency);
  });

Working snippet:

var margin = {
    top: 20,
    right: 20,
    bottom: 30,
    left: 40
  },
  width = 960 - margin.left - margin.right,
  height = 500 - margin.top - margin.bottom;

var x = d3.scale.ordinal()
  .rangeRoundBands([0, width], .1);

var y = d3.scale.linear()
  .range([height, 0]);

var xAxis = d3.svg.axis()
  .scale(x)
  .orient("bottom");

var yAxis = d3.svg.axis()
  .scale(y)
  .orient("left")
  .ticks(10, "%");

var svg = d3.select("body").append("svg")
  .attr("width", width + margin.left + margin.right)
  .attr("height", height + margin.top + margin.bottom)
  .append("g")
  .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

var data = [{
  "letter": "A",
  "frequency": 0.08167
}, {
  "letter": "B",
  "frequency": 0.01492
}, {
  "letter": "C",
  "frequency": 0.02782
}, {
  "letter": "D",
  "frequency": 0.04253
}, {
  "letter": "E",
  "frequency": 0.12702
}, {
  "letter": "F",
  "frequency": 0.02288
}, {
  "letter": "G",
  "frequency": 0.02015
}, {
  "letter": "H",
  "frequency": 0.06094
}, {
  "letter": "I",
  "frequency": 0.06966
}, {
  "letter": "J",
  "frequency": 0.00153
}, {
  "letter": "K",
  "frequency": 0.00772
}, {
  "letter": "L",
  "frequency": 0.04025
}, {
  "letter": "M",
  "frequency": 0.02406
}, {
  "letter": "N",
  "frequency": 0.06749
}, {
  "letter": "O",
  "frequency": 0.07507
}, {
  "letter": "P",
  "frequency": 0.01929
}, {
  "letter": "Q",
  "frequency": 0.00095
}, {
  "letter": "R",
  "frequency": 0.05987
}, {
  "letter": "S",
  "frequency": 0.06327
}, {
  "letter": "T",
  "frequency": 0.09056
}, {
  "letter": "U",
  "frequency": 0.02758
}, {
  "letter": "V",
  "frequency": 0.00978
}, {
  "letter": "W",
  "frequency": 0.0236
}, {
  "letter": "X",
  "frequency": 0.0015
}, {
  "letter": "Y",
  "frequency": 0.01974
}, {
  "letter": "Z",
  "frequency": 0.00074
}, {
  "letter": "LICENSE",
  "frequency": 0
}];


x.domain(data.map(function(d) {
  return d.letter;
}));
y.domain([0, d3.max(data, function(d) {
  return d.frequency;
})]);

svg.append("g")
  .attr("class", "x axis")
  .attr("transform", "translate(0," + height + ")")
  .call(xAxis);

svg.append("g")
  .attr("class", "y axis")
  .call(yAxis)
  .append("text")
  .attr("transform", "rotate(-90)")
  .attr("y", 6)
  .attr("dy", ".71em")
  .style("text-anchor", "end")
  .text("Frequency");

svg.selectAll(".bar")
  .data(data)
  .enter().append("rect")
  .attr("class", "bar")
  .attr("x", function(d) {
    return x(d.letter);
  })
  .attr("width", x.rangeBand())
  .attr("height", function(d) {
    return height - y(d.frequency);
  })
  .attr("y", height)
  .transition()
  .duration(500)
  .attr("y", function(d) {
    return y(d.frequency);
  });


function type(d) {
  d.frequency = +d.frequency;
  return d;
}
.bar {
  fill: steelblue;
}
.bar:hover {
  fill: brown;
}
.axis {
  font: 10px sans-serif;
}
.axis path,
.axis line {
  fill: none;
  stroke: #000;
  shape-rendering: crispEdges;
}
.x.axis path {
  display: none;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js"></script>

Why is this happening?

The way that this is set up means that you're setting the top of the rect to be at whatever y-value relates to d.frequency, and then defining the bottom to be on the x-axis itself (by subtracting the calculated y-value from the max height). Given that before the transition you're effectively fixing the y-value, then getting the height to transition, what you're actually doing is just moving the bottom of the rect, giving the effect you describe.

How can I fix this?

The simplest fix is to transition both the y-value and the height, in a manner that keeps the bottom of the rect fixed. To do this, before the transition simply set the y attr to be y(0), then after the transition(), set the y attr to be the calculated version, i.e. y(d.frequency). Like so:

svg.selectAll(".bar")
    .data(data)
    .enter().append("rect")
    .attr("class", "bar")
    .attr("x", function(d) {
        return x(d.value) - barWidth / 2;
    })
    .attr("width", barWidth)
    .attr("y", function(d) {
        return y(0);
    })
    .attr("height", 0)
    .transition()
    .attr("y", function(d) {
        return y(d.frequency);
    })
    .attr("height", function(d) {
        return height - y(d.frequency);
    });