I followed this workflow successfully with a few large datasets and have now experienced the same problem with a dataset that has 69 000 features. Is there a size/feature limit that can be uploaded?
How are you uploading the shapefile to ArcGIS Online? If you are in a map and clicking 'Add' > 'Add layer from file' then you will have the limitations (1,000 feature max, etc...) that others have mentioned. To avoid these limitations, upload your shapefile to ArcGIS Online as a feature service. Here's how:
1. Go to 'My Content'.
2. Click 'Add Item'.
3. Click 'Choose File' and browse to your zipped shapefile.
4. Check the box that says 'Publish this file as a feature layer'.
5. Set the title and tags as you wish.
6. Click 'Add Item'.
The above procedure will create a hosted feature service from your shapefile, which you can now use in any map you want. On the other hand, adding a shapefile directly to a map only makes that layer usable in that one map, and it throws limitations at you. Always upload data to your 'My Content' area of your subscription. It's a much better way to get things done.