I'm fairly sure that this had to do with the set :keep_releases, 3 that we were using for this particular project. So, the moral of the story is, if you are using Capistrano 2.5.10, be wary of :keep releases screwing up your deploy and leaving you with a current symlink pointed at a non-existant release dir. To fix, update capistrano via:
* executing "rm -rf /path/to/project/releases/(number of release just deployed)" servers: ["the.server.name"] [the.server.name] executing command command finished
and redo your deployment.
gem update capistrano