I'm pretty sure it's France, but I found this from WikiAnswers:
Cinderella dates back many years, even as far back as the Greek and Roman times. The Greeks begin with the story of Rhodopis. She is a servant that is forced to do the laundry in the river while the other servants are at some type of function. An eagle takes Rhodopis's sandal and drops it with the Pharoah, who asks all the maiden's in the area to try it on. Rhodopis is the first one the sandal fits. They fall in love and are married. There are many other origins that appear at later dates such as the Chinese, Ye Xian, into the Phillipines, Japan, and Germany, where the famous Brother's Grimm story comes from (the one where the stepsisters have their eyes pecked out by birds). Overall, according to Joanna Cole, an author of folklore collection, there have been over 325 known versions created from all over the world since 1825. All versions vary with details. For example, the French version suggests that one of the stepsisters was actually kind to Cinderella. The Brother's Grimm do not mention a fairy godmother at all; instead, the mother's dead spirit tends to control the events that unfold for Cinderella.