The problem is not the baseline of the \resizebox but the baseline of the tabular which is on its center by default. So changing the baseline of the tabular with [b] solves this issue:
\documentclass[twocolumn]{article}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{subfig}
\pagestyle{empty}
\begin{document}
\begin{figure}
\centering
\begin{tabular}{cc}%
\subfloat[]{%
\fbox{
\resizebox{0.5\linewidth}{!}{%
\begin{tikzpicture}
\node {a};%
\end{tikzpicture}%
}%end resize
}%fbox
}&%end subfloat
\subfloat[]{%
\begin{tabular}[b]{c|cccc}% === [b] added here ===
& 0 & 1 & \dots & n\\\hline
a & & & &\\
b & & & &\\
c & & & &\\
\dots & & & &\\
d & & & &\\
\end{tabular}%
}%end subfloat
\end{tabular}%
\caption{Why resizebox shifts the baseline up?}
\end{figure}
\end{document}

Addendum 2013-01-04:
As user adn has found out, the captions are still not perfectly aligned. (See comments below.) A possible solution would be switching to the subcaption package resp. its \subcaptionbox command:
\documentclass[twocolumn]{article}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{subcaption}
\pagestyle{empty}
\begin{document}
\begin{figure}
\centering
\begin{tabular}{cc}%
\subcaptionbox{}{%
\fbox{
\resizebox{0.5\linewidth}{!}{%
\begin{tikzpicture}
\node {a};%
\end{tikzpicture}%
}%end resize
}%fbox
}&%end subcaptionbox
\subcaptionbox{}{%
\begin{tabular}{c|cccc}%
& 0 & 1 & \dots & n\\\hline
a & & & &\\
b & & & &\\
c & & & &\\
\dots & & & &\\
d & & & &\\
\end{tabular}%
}%end \subcaptionbox
\end{tabular}%
\caption{Why resizebox shifts the baseline up?}
\end{figure}
\end{document}
Please note that changing the baseline of the inner tabular (with [b]) is not necessary here since a \subcaptionbox always has its baseline between content and caption, and therefore the two \subcaptionboxes are already aligned by default.
\fbox{by adding%there as well. Note that with theadjustboxpackage you can simply write\adjustbox{width=0.5\linewidth,fbox}{..}or\begin{adjustbox}{width=0.5\linewidth,fbox} .. \end{adjustbox}and easily add more modifiers. – Martin Scharrer♦ Jan 3 at 9:33