Could be a multitude of different things. Do you have viewstate disabled for any of the parent containers (webpart zones, page template, etc.)? How about the webpart itself, do you have viewstate disabled? Do you have invalid HTML on the page like a
<form> tag nested inside the page somewhere? Also, are they navigating back to the page using the back button after the form has been submitted? This may be another issue, you might try wrapping a update panel around the form.
Typically those are the issues I see with this type of issue.