Проблема заключалась именно в том, что скрипт запускался из под www-data и необходимо было генерировать отдельные ключи для ssh для данного пользователя.

Проблема была связана с переводом часов 26 октября 2014 года. Решилось обновлением библиотеки libicu52.