i actually had this happen to me a while ago, second day i had the phone i think.
anyway if i'm right if you go into your storage and look at what's using it it wont even report that it's full or anything near being full.
i cant remember for sure how i fixed it, but i think i cleared data in google play and uninstalled updates then tried again.
i think before i did that i went and deleted everything because i thought it was actually somehow full, but it was just a waste of time.