We've encountered the same problem but have found a workaround. The problem seems to surface when the Use box within the Change Symbols box is set to "A Single Symbol". When you get to the Change Symbols box, make the Use field "Unique Symbols" and then choose a field from within your dataset upon which to base your symbology. Before uploading a shapefile, I've taken to adding a field that contains the same value for all records. When I change the symbology within arcgis online, I base the change on this field and it allows me to give the same symbology to all records.
... View more