Once I had my app rejected from Google Play, because they decided it was plagiarizing another application... which was actually the very same application posted by me somewhere else. Took some effort to convince them that I'm me, even despite of my Google account being registered on a domain that's prominently displayed as the first thing after launching the app.

Another time, they suddenly decided that "No information is gathered from users whatsoever." is not a valid privacy policy for a Free Software application that does not gather any information (it was a simple game that couldn't even store highscores locally).