Arduinos fly in rockets just fine. Yesterday I sent my 4" 10lb Patriot up to 2500' on a J440. It was a bit windy, so I used a smaller motor than I'd originally planned. In the nose was a serial arduino with a radioshield connected to a Garmin GPS18 and a ham radio for tracking. That particular rig not only survived that, but several previous flights to higher altitudes (5000+ ft), including one where the main failed to deploy and it hit the ground (salt, actually, at the Bonneville salt flats) at 50+MPH. That impact bent some pins on the shield because the bulkhead broke loose and tried to go out the side of the nosecone, but it was otherwise undamaged.
Relays are not a good idea in a rocket, as G forces and vibrations beyond a typical relay's ratings may be encountered. Use something solid state, such as a FET like grumpy_mike described.
If the circuit will be anywhere that it can cause the flight to fail unsafely (e.g. fail to deploy a chute because the second stage motor didn't ignite), don't do it.
A pair of CR123A batteries are smaller and provide much more current than four AAs, while providing the same voltage.
If you change igniters, make sure they're compatible with your motor.
but I'd have expected the second stage to be triggered by the first stage separating, and I'd expect that to be triggered somehow by the expiry of the first stage.
That's how it happens on model (e.g. Estes sized) rockets. A special first stage motor burns through the top and lights the next stage.
Doing it based on a timer somehow doesn't feel like a good way to synchronise the handover to the next stage.
Works for NASA - that's how they stage their multi-stage sounding rockets (and deploy payloads, parachutes, etc). High power rocketry also uses timers for staging. As a matter of fact, I just bought a couple of commercial units. Haven't even used one yet, and I'm already planning to make my own, probably arduino-compatible. 
-j
