Then he found out about OpsWorks. We had our apps deployed in a single day and migrated over by the end of the week. There was a bit of learning to deal with Chef, but it was an overall smooth experience.
We've linked it up to Codeship and now we simply push to Github, Codeship runs our test suite, and they run a rake task to initiate a deploy via OpsWorks. Ever since Codeship made some serious optimizations in the past week, our time from git push to deploy is about 5 minutes. Awesome!