I have this exact issue but the solution has not been discovered: http://social.msdn.microsoft.com/Forums/en-US/sharepointcustomizationprevious/thread/021c6c2d-4bdb-4e76-a48a-a51502fc809a/
The issue is that I try to delete a column from a list, and I get an "Invalid Viewstate" when looking at the ULS logs. My masterpage is custom and has no searchbox in it as described in the post above. I have narrowed the problem down to 2 custom visual webparts on the masterpage. Both have to be removed from the page, in order for the column to be deleted.
It does not make sense to me, so I wanted to ask you all.