I have experienced the same problem or a very similar problem, I have been working with a colleague conducting field surveys in areas with poor internet connection, we have been using feature data sets that have been uploaded to ArcGIS Online and set up for 'Offline' editing and syncing. I have been using a mini iPad with Bad Elf GPS receiver and have had no issues with syncing, my colleague on the other hand is using a Samsung table and has had intermittent issues with syncing. In one particular data set, the first round of surveyed records collected were fine, then on a return visit to the same site an extra thirty two features were captured and 'submitted' but when the sync was attempted it failed. It seemed to go through the same process as you have described, started the process, you could watch the circle going around and then it takes ages and finally fails.
Anyone have any ideas?
