I've encountered this error occasionally with different map packages given to me by individuals, for publishing to ArcGIS Online. Each situation has been a case of something peculiar about the package the AO didn't like, and I've been able to publish the contents of a finicky package using one of the following methods: 1) delete extraneous layers you don't need to publish 2) if Step 1 doesn't work, divide a map package containing feature layers and tile layers into one file for the former and one for the latter, and publish each to a feature service or tile service accordingly 3) as a last resort, rebuild the map package by importing the layers into a new file
... View more