For what it's worth, I had the same problem.
Strange thing was, I had 2 gridviews on one page, one worked the other only worked after 1 postback.
Couldn't figure it out, even if the gridview was placed on its own page it still didn't work correctly after the first postback. One thing to note (I don't know if it's important) is that the gridview that didn't work correct returned way more records than the one that worked.
Also try to do a databind in the pageload or prerender, that seemed to help somewhat (not enought for me...).
denloof