Deciding whether a metric is a tree metric An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, i.e. a metric is a tree metric iff every 4 point subspace is a tree metric. In particular this implies that one can decide in polynomial time whether a given metric is a tree metric by examining all quadruples of points in the space.
My question now is what other (than the trivial) algorithms are there? Can one check in linear (in the number of points) time whether a metric is a tree metric?
If the given metric space embeds into a tree metric, the tree must be its tight span. The O(n^2) time algorithms referred to in Yoshio's answer can be extended to certain two-dimensional tight spans: see arXiv:0909.1866.

One method for solving the problem is incremental (as in the linked preprint, but much simpler): maintain a tree T containing the first i points from your metric space (that is, having the same distances as the corresponding entries of your input distance matrix) and extend it one point at a time; at each step there's at most one way to extend it.

To test whether to attach your new point r along edge uv of your existing tree, find points p and q of your metric space that are on opposite sides of edge uv. The new point attaches to a point inside edge uv iff d(p,r) > d(p,u) and d(q,r) > d(q,v); using this test on each of the edges of the existing tree, you can find where it attaches in O(n) time. Once you've found where to attach it you can test in O(n) time whether the distances to all the other points are correct. So each point you add takes time O(n) and the whole algorithm takes time O(n^2), optimal since that's the size of your input distance matrix.