I'd tend to agree with the others that the problem is pretty similar to Sorites. I would also add that you seem to be getting at the idea of essentialism - that there is an essence of what it is to be a watermelon that is needed to say something is a watermelon. You (like the ancient Greeks) are trying to come up with necessary and sufficient criteria for watermelonhood. I think that this is a common philosophical muddle and let me outline why I think the problem dissolves if you consider the use of language.
Instead of assuming that behind the word "watermelon" is some entity that must be common to all things we correctly call watermelon. Instead it could be helpful (in Wittgenstein style) to consider the meaning of "watermelon" as bound up in its use. So in answering the question "when does a watermelon cease to be a watermelon?" , we should consider the context. Consider the following examples:
It's your girlfriend's dad's birthday. She asks you to buy watermelon for the dessert because her dad loves watermelon. You are agreeable, and head to the shop, pick up the watermelon, and head back. On your way back you bump into your friend who suggests having a game of throwing/punting/kicking and you have no football so you suggest using the watermelon (you're an asshole). You kick it around a bit, leaving bits of melon all over the gravel, your clothes etc. After a while you realize you'll be in trouble so you scrape up the bits and pieces of the gravelly, mutilated watermelon into your shopping bag and head home. When you show your girlfriend the bag with red liquid in it, she shouts "What?!! I told you to get a watermelon, that's not a watermelon!"
Is she wrong to say that? I don't think so.
Consider, on the other hand, a scientist working on watermelon cells. She has in her fridge slides with watermelon cells, slides with human cells, tomato cells, etc. She is looking through the microscope at a flea cell and calls her assistant, saying "Get me the watermelon".
Is this use wrong? Again, I think not, despite the fact that, on a superficial view, the second is much less similar to the everyday watermelon. Context is everything. You need to ask, what are you doing with the word? That determines what your answer is.
Consider one last example. Your friend is a watermelon connoisseur, and you want to impress him, bringing an expensive watermelon over for him to taste. Being a snob, he tries some, looks disparagingly at you combined with a smug grin, and says " listen dude, that's not watermelon", and gestures to his basket of premium watermelons on the table.
Again, I think that it's perfectly clear what is meant in that case.
