Character table does not determine group Vs Tannaka duality From the example $D_4$, $Q$, we see that the character table of a group doesn't determine the group up to isomorphism. On the other hand, Tannaka duality says that a group $G$ is determined by its representation ring $R(G)$.
What is the additional information contained in $R(G)$ as opposed to the character table? 
 A: It might be worth explaining why you shouldn't expect $R(G)$ to tell you everything about a group.  $R(G)$ is naturally isomorphic to the ring of class functions $G \to \mathbb{C}$ (the functions constant on conjugacy classes) under pointwise addition and multiplication, and as such the information it contains is precisely the multiset of sizes of each the number of conjugacy classes of $G$.  That's it!  No other information.  (Note that $D_4$ and $Q$ both have conjugacy classes of sizes $1, 1, 2, 2, 2$ five conjugacy classes.)  
In other words, the abstract structure of the representation ring actually gives you less information than the character table; the character table at least hands you a distinguished basis of $R(G)$.  Without this basis, $R(G)$ can't even tell you what tensor products of representations look like.
A: Let me try and give as low-level an explanation as I can, in case you're scared of all this "monoidal category" stuff.
A complex representation of a finite group $G$ is just a module for the group ring $R=\mathbf{C}[G]$. The two groups you mention with the same character table have isomorphic group rings as well (by some abstract structure theorem for simple $R$-modules), so, if you fix an isomorphism between the group rings you have a way of moving from a representation of one to a representation of the other!  Let's call this way of moving between representations of the groups "the trick". The representation theory of both groups is very close because we can use the trick.
However the way to spot the difference in the representation theory of the two groups is to use the tensor product. If $M$ and $N$ are representations of $G$, then one can give $M\otimes_\mathbf{C} N$ the structure of a representation of $G$, but this construction must use "more than the abstract $R$-module structure of $M$ and $N$". What I mean by that is this: if $R$ is a random non-commutative $\mathbf{C}$-algebra and $M$ and $N$ are two $R$-modules, there's no natural way (that I know of) to give $M\otimes_\mathbf{C}N$ an $R$-module structure. The way this works with $R=\mathbf{C}[G]$ is that you let $\mathbf{C}$ act in the obvious way (i.e. on one of the factors) and let $G$ act diagonally (i.e. on both of the factors at once). This is a big asymmetry and we're using the fact that $R=\mathbf{C}[G]$ (i.e. that $G$ gives a basis of $R$) rather than just its abstract ring structure. 
Because the groups you mention have the same character tables, it's true that if $M$ and $N$ are modules for one, then using the trick they're modules for the other. But the shocker is this: the trick commutes with tensor products! (at least up to isomorphism).  Because the character of the tensor product is the product of the characters! So applying the trick to $M\otimes N$ gives a module that happens to be isomorphic to the tensor product of the tricks applied to $M$ and $N$. So now the representation theory of the groups is looking really close.
But the trick is not canonical, it involves a random choice of isomorphism between the two representation rings, and so when you actually start drawing bunches of natural isomorphisms that Tannakian categories are supposed to satisfy, they don't commute with the trick, because the "(at least up to isomorphism)" remark comes back to haunt you. This is my understanding of the explicit point where the subtlety is buried. I should say however that I figured all this out myself once and I might be wrong. If I'm wrong I will no doubt shortly be put right!
A: It might be worthwhile to supplement Kevin Buzzard's answer by describing exactly what goes wrong in the case of $Q$ and $D_4$. Let $V$ and $W$ be the two dimensional irreducible representations of $Q$ and $D_4$ respectively. 
The representation $V \otimes V$ is isomorphic to $1 \oplus \chi_1 \oplus \chi_2 \oplus \chi_3$, where the $\chi_i$ are the nontrivial (one-dimensional) characters of $Q$. Similarly, $W \otimes W$ is isomorphic to $1 \oplus \eta_1 \oplus \eta_2 \oplus \eta_3$ where the $\eta_i$ are the nontrivial (one-dimensional) characters of $D_4$. The reason these formulas look the same is that the representation rings of $Q$ and $D_4$ are isomorphic.
However, we cannot build this isomorphism out of maps of vector spaces which commute with tensor product. Specifically, we cannot find an isomorphism $\alpha : V \to W$ of vector spaces so that the induced map $\alpha \otimes \alpha : V \otimes V \to W \otimes W$ carries $1$ to $1$ and $\chi_i$ to $\eta_i$. (Of course, I haven't told you how to label the $\chi_i$ and $\eta_i$. My statement is that there is no choice of labeling for which you can do this.)
This is very easy to see. The map $\alpha \otimes \alpha$ will carry the anti-symmetric elements of $V \otimes V$ to the anti-symmetric elements of $W \otimes W$. But $\wedge^2 V$  is the trivial representation, and $\wedge^2 W$ is not! So isomorphisms of the form $\alpha \otimes \alpha$ can't carry $1$ to $1$.
A: An  RWTH Aachen thesis by Helena Skrzipczyk [1992]  is referred to by Eick and J. Mu"ller
J. ALg 304 (2006) On Brauer pairs. She gives several examples of non-isomorphic groups with
bijections between the character tables and power maps. They are the smallest order Brauer
pairs assuming such to be p-groups.
A: If I'm not mistaken, the extra information is not contained in the representation ring, you have to look at the category of representations. In particular, you want to look at the representation category equipped with its forgetful functor to vector spaces. Then the group can be recovered as the automorphisms of this functor. Here's a blogpost I wrote which may be helpful: http://concretenonsense.wordpress.com/2009/05/16/tannaka%E2%80%93krein-duality/
A: Regarding a question which arose in comments to another answer: The lambda ring structure is on $RG$ is not enough to reconstruct the group. Dade has given examples (MathSciNet review here; paper here) of pairs of groups which have the same character table with the same power maps, and from this it follows that the whole lambda ring structure is the same.
A: Edit:  Somehow I totally misread the question.  I talked about the group algebra $\mathbb C[G]$, which is not at all the same as the character ring $R(G)$.  Over $\mathbb C$ (or any other field of characteristic 0), $R(G)$ is naturally a subalgebra of $(\mathbb C[G])^*$, which is the algebra of functions on $G$ with pointwise multiplication, and now the comultiplication encodes the group structure.  On the other hand, it is not a subbialgebra: the coproduct of a class function is not a class function.
Anyway, original post below, with the obviously wrong things struck out.  So it's really an answer to Kevin, rather than anything else.

Well, it depends on what you mean by "$R(G)$".  I won't address TK duality, and most of what I'll say is essentially a follow-up to Kevin's answer, rather than an answer in its own right.  Also, I'm only going to address finite groups and their finite-dimensional representations.  Also, for me the word "ring" means (associative, unital, noncommutative) "$\mathbb C$-algebra".
Recall that a complex representation of $G$ is the same as an algebra representation of $\mathbb C[G]$.  Let $R$ be a ring.  As Kevin says, it's in general impossible to define an $R$-module structure on $M\otimes N$ when $M,N$ are $R$-modules.  (When $R$ is abelian, which is not the case here, one can define a tensor product $M \otimes_R N$, but that's not the tensor product of representations anyway.)  What would a tensor product of modules require?  It would require a rule that assigns to each $r\in R$ and each pair $M,N$ of $R$-modules an endomorphism of $M\otimes N$, of course, and we should impose all sorts of axioms that force the tensor product to be well-behaved.  Among other things, it's much easier if the endomorphism is an element of the tensor product $\text{End}(M) \otimes \text{End}(N) \subseteq \text{End}(M\otimes N)$.  And we already have some distinguished elements of $\text{End}(M)$ and $\text{End}(N)$, namely the action of $R$.
So one way to try to construct a well-behaved tensor product on the category of $R$-modules is to find a nice map $\Delta: R \to R\otimes R$.  Then the axioms for this map that assure that the tensor product is good are that $\Delta$ be an algebra homomorphism, and that it be "coassociative": $(\text{id}\otimes \Delta)\circ \Delta = (\Delta \otimes \text{id})\circ \Delta)$.  Let's suppose that there's also a distinguished "trivial" representation $\epsilon: R \to \text{End}(\mathbb C) = \mathbb C$; if this is to be the monoidal unit, then we'd need $(\text{id}\otimes \epsilon) \circ \Delta = \text{id} = (\epsilon \otimes \text{id})\circ \Delta$.  The maps $\Delta, \epsilon$ satisfying these axioms define on $R$ the structure of a bialgebra.
By the way, the map is called "$\Delta$" because if $G$ is a group (or monoid) and $R = \mathbb C[G]$, then the map $R \to R\otimes R$ given on the basis $G$ by the diagonal map $\Delta: g \mapsto g\otimes g$ is such a structure.
Then here's a cool fact.  Define an element $r\in R$ to be grouplike if $\Delta(r) = r\otimes r$.  Then the grouplike elements are a multiplicative submonoid of $R$.  And when $R = C[G]$, the grouplike elements are precisely $G$.
So my answer to your question is that "the additional information contained in $R(G)$ as opposed to the character table" is its bialgebra structure.
