A few things to check:
Look for spaces in the column headings. Remove them.
Also, case matters. SKU is not the same as sku. (Occasionally, Magento will forgive case errors—but uploads just run more quickly if the data is clean.)
I have better luck with CSV than I do XML. Excel is simply horrible at UTF 8. I assume that it is not UTF-8, even if it says it is.
The trick I use is opening the file in the Open Office spreadsheet program, which saves nicely in UTF-8. If you have columns of numbers, format them as text. I still edit in Excel because I know it better, but a final clean up with Open Office has reduced errors a lot.
Other folks use Notepad to open their CSV file and re-save it as UTF-8. This also works.
If you are creating new products, include every column from your original download sheet. Not all the columns are mandatory, but if a required field is missing the sheet will not upload correctly. They do not have to be populated, but the headings must be there.