hmm interesting. Okay just put a $conf['imconvert'] = '/usr/bin/convert'; into your conf/local.php and see if works. Also could you try what the following PHP file tells, when called from your server?
<?php
$file='/usr/bin/convert';
if (file_exists($file)) {
echo "The file $file exists";
} else {
echo "The file $file does not exist";
}
if (is_readable($file)) {
echo "The file $file is readable";
} else {
echo "The file $file is not readable";
}
if (is_executable($file)) {
echo $file.' is executable';
} else {
echo $file.' is not executable';
}
?>