Here's another problem that is equivalent to this one (see http://www.cs.huji.ac.il/~nati/PAPERS/gotsman_equivalence.pdf):
Consider a 2-coloring of the vertices of the n-dimensional hypercube. We say that it has a monochromatic k-star if there exists a vertex that is colored by the same color as at least k of its neighbors. Since the Hypercube is bipartite we can have a coloring without even a monochromatic 1-star -- this coloring will be exactly balanced (i.e. exactly half of the vertices get each color). What about non-balanced colorings? Define s(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a monochromatic s(n)-star. It turns out that s(n) is equal to the minimum possible sensitivity of a Boolean function of degree exactly n. [The basic idea is to look at the product of the coloring (viewed as {-1,1}) with the parity function on the n bits. The non-balancedness translates to full degree and the k-star translates to sensitivity k.]
A related problem defines r(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a r(n)-star of the majority color. This was studied by Chung, Furedi, Graham, and Seymour in 1988 (see http://www.math.ucsd.edu/~sbutler/ron/88_06_induced_cube.pdf ) who give essentially the same bounds as known for s(n). Thus it is known that log n <= r(n) <= s(n) <= sqrt(n), and the conjecture is that both are at least n^a for some a>0.
