Having come across this several times and forgotten how I'd fixed it, I figured this will help more than a few...
The problem occurs in Buttons, DataGrids and other event driven controls in Web Parts and Controls. On the first time through, the primary event (like the Click event on a button), the event does not fire. On the second click however, everything seems fine. If you follow through in Debug, you'll file that the event is actually skipped and the control proceeds to the render event.
In most cases, the fix is simple: one of the controls within the control/web part has AutoPostBack = true where it doesn't need it. Typically, this is a cut and paste error - for example, adding AutoPostBack to a TextBox.
This, by the way, though very odd, is somewhat expected. The invalid postback on the control tells ASP.NET that it's already happened, when indeed it hasn't since the specific control cannot perform the actual postback.