It's a little late, and I'm not sure if you'll still be interested, but I too was keen to build a Turtle robot based on the Arduino for my kids. I've been building it for a while now and thought you might be interested - it's open source (or it will be when I put the designs online shortly) and pretty easy to build. It's WiFi based and battery powered. I've also built a Logo virtual machine that runs on the Arduino which lets you hook up commands to do whatever you want really.
The robot is here: http://mirobot.io
and the Logo VM is here: https://github.com/bjpirt/LogoVM
Give me a shout if you're interested and I'll happily send across the designs (they'll be online in the next week or so anyway)