When to automate? I'd advotcate for sooner rather than later, but of course our std answer can be put in here... "It depends".
If its a GUI app, where not only does the Look and feel change, but controls and fields appear/disappear at will, then I'd say wait for things to firm up a bit before doing a lot of your GUI automation. But who is to say that that GUI will not radically change down the line, incurring a hefty maintenance cost?
If it is more along the lines of API testing, I'll say you can start writing your automated tests and create teh framework even before dev has completed its code.
If you have a solid spec, you can also start automation here right away as well. The better defined your final product is, the sooner you can start automation.
But don't lose sight of my number one idea.... it all starts with a good test plan. Without one, automation efforts have a greater chance of being wasted, spinning your wheels in no-mans-land. Define what you need it to do, and why it needs to be done. Then think about how you can implement your solution.
I've been pretty lucky on my latest project where we send an XML stream to another computer based on some well-defined query language. My tests and verification routines were done in a week and a half. Well before I got code from dev. Anytime they make a change in the stored procs, I still can verify that the results returned in the XML stream make sense in less than 5 mins. And this is for several hundred test cases. Powerful indeed. But only because the product is ultra well defined, and I had a kick-a$$ test plan to work from.
Good luck!