This suggests that the email attribute isn't being saved correctly.
You haven't mentioned whether it's flagged in an in-page validation (i.e. the field is highlighted), or in a post-process error message (the page reloads and an error message is displayed). These two circumstances would require vastly different solutions.
If order for better debugging, you'll need to provide much more detailed information. We'll need to know if you are using any custom or third-party checkout modules, and if any attribute modification has happened during the production of the store. This could also be an issue with the template, so I'll try and cover all bases in my answer.
If the error is flagged during in-page validation, you'll want to visit the phtml file of the checkout and ensure that it's validation settings are correct. The field's classes should be:
class="input-text required-entry validate-email"
Post Process Issue
Without knowing more about your store, and whether or not you're using a custom checkout module, you'll want to check against the following (there's a range of issues that it could be indicative of):
The name of the field in the phtml file.
If the name of the field is incorrect, then the value won't be received correctly in the backend process.
The email attribute in the database.
Check the email attribute is set correctly in the database. In the
eav_attribute table, the
email attribute should match many of the settings of any of the other 'required' customer fields (such as firstname or lastname) - denoted by
Receiving the data in the controller
When a process is submitted, it gets posted to a specific URL. This URL can be matched to a Controller and an Action. Within the action, you'll be able to utilise the following method to ensure that the attribute itself is being posted to the controller:
This will print out every single variable that gets posted to the controller action and if email is not present, then this would suggest the issue is on the template itself.
Whilst this answer in itself isn't definitive, I hope it provides you with a bit more information and some guidance on where to look for the error.