Ok, only Ryan wrote to me about the solution. Anyway, here is the solution:

Let n be the number of vertices in the graph, and let S be the solution set, if one exists.

First, note that for each edge, at least one of the ends should be in S (cause S is a vertex cover), and not two of them are in S (cause S is an independent set). So, if S exists, the graph should be two-colorable. i.e., it's bipartite.

Second, for every graph, |max-independent-set| = n - |min-vertex-cover|. So, if S exists, |S| = n - |S| or |S| = n / 2.

Third, for every bipartite graph, |min-vertex-cover| = |max-matching|. This is a widely known result, or you can work it out yourself, but it's a bit nontrivial at first (unless you think about incremental paths.) So, if S exists, |S| = |max-matching|.

From the three paragraphs above, we deduce that if S exists, the graph should be bipartite and have a matching of size n / 2. In other words: the problem has a solution only for bipartite graphs with perfect matching. If we have such a graph on the other hand, any of the two parts is indeed both a max-independent-set and min-vertex-cover, and so a solution.