Domotorp and ARupinski likely know this already, but I thought I would record this as an initial foray into cornering a counterexample by a process of elimination. I will not bother with the general case, but focus on the specification of 256 out of 512. Let G be the collection of all bipartite graphs with 256 edges.
I will consider bipartite graphs only, and my concern is with the size of the smaller vertex set and how many edges can come from it. Certainly any node with degree at least 256 will contain an induced subgraph from G. Further any two nodes in the small set with combined degree of 256 or greater will also contain a subgraph from G. There is likely a better characterization than the following: any three vertices with combined degree of 383 and any 4 vertices with combined degree of 510 will produce a subgraph from G. (Note I am focusing on small independent vertex sets.)
Of course we can ignore vertices of degree 0. If we can characterize nicely the graphs with, say, an independent set of 3 vertices and a large number of edges (but fewer than 383) which do not have a subgraph from G, we might be able to use this to classify such graphs with larger independent sets, working our way up to 23 vertices, the rough square root of 512.
EDIT 2012.11.11 Unfortunately the analysis below is not quite right. One can find a subgraph of $K_{4,96}$ with $3*96=288$ edges which contains no induced subgraph from G. It turns out that if there are enough edges and the degrees of the larger set are anything but a multiset of 3's with at most one 2, then the conclusion holds and indeed $267$ edges are enough. I am confident that this line of investigation will produce something useful, but the treatment below is not enough. In particular, I am now unsure there is no counterexample which is not a subgraph of, say, $K_{7,n}$ for some $n$. END EDIT 2012.11.11
EDIT 2012.11.09 This problem is not exactly one about submultisets of integers and number theory, but taking that slant cuts a wide swath in the forest of bipartite graphs on 512 edges.
The major reason for needing 382 edges coming from 3 independent points while requiring less than 270 points coming from 4 independent points can be viewed as purely number-theoretic: given a=3 and b=127, there are no integers c and d such that $0 \leq c \leq a$ and $0 \leq d \leq b$ and $cd=256$. So $K_{3,127}$ is a graph of 381 edges which has no induced subgraph belonging to G. However, number theory can be used to show 382 edges from 3 points suffice, as we can either remove one of the three points and work with the remaining 2, or we look at the one point with degree 128 and note it has enough neighbors of the right degree that we just need to remove neighbors of degree 3 (or smaller degree if we run out) to achieve an induced subgraph from G.
That 4 points requires a lot fewer edges results from just needing enough residue classes mod 4 to take care of any problems: either there is a $K_{4,64}$ subgraph hidden, or there are at least enough vertices of degree 1,2, and 3 to adjust the sum mod 4. As a result, it is clear that $252+ 4*3$ is enough edges to find a subgraph from G, so let's be generous and say a combined degree of 280 suffices for 4 vertices.
We can now leverage that estimate and say that for 5 (and 6 and 7) vertices that 350 (and 420 and 490) edges respectively between them are enough to find a subgraph from G, either by removing neighbors of the 5 vertices, or by removing the vertex among the five with smallest degree, reducing it to a previous case.
Since 8 divides 256, we need either find a subgraph of the form $K_{8,32}$ or enough vertices of smaller degrees to finish the job. Rough estimates give 304 as a sufficient combined degree, which we can now leverage to say that no counterexamples on 512 edges from 13 vertices will be found.
Likely we can extend it by analyzing the case of 12 vertices further, but I will save that for later. I now suspect that domotorp will not get his counterexample for bipartite graphs with $2^n$ edges for $n \lt 10$. END EDIT 2012.11.09
Gerhard "Inching His Way Toward Bounty" Paseman, 2012.11.08
