How to Remove "Other" data on iPhone 5s still on phone after Restore to "New Phone Setup?"

Hi,

I am trying to remove 800MB of mystery "Other" data on my iPhone 5s that will not go away after I performed 2 Restores back to factory settings in new iOS software as of 04-09-14 and chose "Setup as new phone". There is no personal info on the iPhone 5s yet but it still shows 800MB of "Other" data.

Last week I noticed that I had 4GB of "Other" data on my iPhone 5s. After performing 1st Restore this morning, my iPhone 5s was auto upgraded to new iOS as of 04-09-14. My "Other" data went down to 1GB from the 4GB.

After running PhoneClean app, which I bought, I got the empty iPhone 5s down to 800MB of "Other" data, and performed 2nd Restore back to factory settings in new iOS software as of 04-09-14 and chose "Setup as new phone".

It's still at 800MB of "Other" data.

I don't believe the new iPhone arrived with that much "Other" mystery data.

Any help would be greatly appreciated,

Thanks

Matt