I've found out what the shared host problem was. I must have upgraded my local copy of Capistrano to the latest. Which changes the permissions used on deployment - instead of 755 they are 775. This causes problems on shared hosts because it effectively means you can execute scripts on other people's accounts. So a patch has been submitted for Capistrano and you need to add the following to your deployment script.
task :set_permissions do
donothing = true