Dear All,
I also had the same problem and i tried alot but fortunately eventually i could find the solution .I export the shapefile in Arcmap and then kept only DBF File,PRJ FILE,SHP FILE AND SHX Files and removed other files like SBN ,SBX etc.. Then ,I select all files and right clicked and zipped them .And I add the zipped shapefiles in ArcGIS online from my desktop and it worked for me and i hope, it works for all. Remeber just zip files not folders.
Regards,
Ahmad Javed Gulistan,
Kabul,Afghanistan