Arduinos aren't vert good with cameras. Not enough RAM to buffer the image.
Why does everyone keep forgetting about the Nootropic Design Video Experimenter kit?
http://nootropicdesign.com/ve/It's built on the back of a modified form of the TVOut library; that said, you likely won't have much code (or more likely, SRAM) room left over for the rest of your custom code (and you can't use a Mega with it) - but maybe you could devise a way to use one Arduino dedicated to the VE, and communicate with it via another Arduino (with your code on it).
Other options would be to build something like the AVRCam:
http://www.jrobot.net/Projects/AVRcam.html...which is kinda like the CMUCam system, just lower cost (plus you have to build it yourself - no kits or other ways of buying it, AFAIK)...