I also found that the issue is caused by the DataValidation tags. So far, I have been unsuccessful in changing the XML code so that any Excel 2010 client may open the file regardless of Protected View options.
However, I can offer another work-around that does not require disabling Protected View. After saving the XML file to your harddrive, right-click the file and select "Open with..."->"Internet Explorer". IE opens it like normal, and the user can edit/save. Once the file is "natively" saved once on the machine, Excel 2010 opens the file as expected (the first save essentially turns off Protected View for subsequent viewings).
If you found a way to edit the XML Spreadsheet 2003 code so that it opens without needing a work-around, then please mention it in the comments.