I don't have any children of my own, but that's no reason not to experiment on other's children! So here's my story: My younger brother got his first computer back when he was 7 years old. It was an Asus bare-bone computer which had problems with ACPI and Windows XP. In the end after about a month of trying I gave up on installing Windows on his computer (it came with Xandros preinstalled) and I installed Fedora 2.
The experience was mostly positive. He liked the centralized package management and localization (which was then almost non-existent for my language for windows and windows programs) made everything much easier for him. Also almost all windows programs he wanted to use worked with wine.
In the meantime he switched over several computers, but all of them had some GNU/Linux distribution installed on them. The result is that nowadays he's very comfortable with GNU/Linux and OpenOffice, so I believe I can say that the experiment was a success.
Keep Up with TechRepublic