You define the definition of done. But it should include everything to make it completely done. "I'm sorry, I've forgotten to implement validation for that input control" means your story is not done, so should it put back in the in progress column. If you discovered that after the sprint, it's a bug that the PO can address (or not) in the next sprint. The PO eventually decide if you ship the product at the end of an iteration.
Like you said, testing comes after code has been written for a given user story. But testing should be a part of your definition of done.
Therefore, done completely is the state you get when a user story matches your definition of done.
Given they've just been given the story during planning (regardless of it being a new story or not having estimated it earlier) you have a few choices.
First, you can ask the product owner if the story can be left on the backlog so that it can be properly checked and estimated during this sprint, and take it next sprint.
If that's not possible, another option is to do it in a spike - a time-boxed story to investigate something or to try something out - and then you'll have a head start for doing it next sprint.
Finally, if you really must start on it this sprint, then try and find out as much as you can during planning, and take the story but make it clear of the risk that it may not be completed this sprint. If it doesn't get completed, so be it, you've done some of it and now know a lot more about it for the next sprint.
Remember, estimates are just the best estimates with the information you have at the time, and can be revised later when you have more info.
Also remember you should be spending about 5%-10% of the sprint in refining the backlog. Doing this really helps keep the planning meetings shorter, more focused and more productive.
Best Answer
I am in favor of locking down stories fairly quickly in their life cycle. Requirements should be set after less than a day's worth of discussion in most cases. After that point, it's up to the product owner to decide if those requirements are actually something they want. If they aren't, cancel the story. If they are something they want or partly what they want, complete that story, and create a new story for the following changes.
When in doubt, fight for creating a new story. Constantly changing the requirements just keeps moving the goal posts for the developers. That isn't fair to them, and it's bad for morale.