Добрый день!
Правильнее, чем написано в документации http://api.mail.ru/docs/gui... в разделе Подпись запроса# вряд ли удастся ответить. Проверьте все ли параметры участвуют в формировании вашей сигнатуры, чаще всего ошибаются в этом.

Отчасти дело было действительно в параметрах, не хватало uid. Возможно кому-то пригодится эта информация. Простой пример для публикации обычной текстовой строки $text методом Сервер-Сервер (без session_key с параметром secure=1):

app_id - код приложения
uid - код пользователя, от имени которого происходит публикация (владелец группы и владелец приложения)
uid2 - код группы, в которую идет публикация
text - собственно текст публикации (RAW и/или http-link)
app_secret - секретный ключ приложения (НЕ приватный)



function post($text)
{

$app_id = '7****7';
$private = '3***********************5';
$app_secret = '8*******************************e';
$uid2 = '7************************9';
$uid = '2*******************2';

$params = array(
'method'=>'multipost.send',
'app_id' => $app_id,
'uid' => $uid,
'uid2'=> $uid2,
'text'=> $text,
'secure'=> 1
);

$url = mailru_getUrl($params,$app_secret);

//дальше делаем запрос например CURL'ом по этому $url
}

function mailru_getUrl($params,$secret_key)
{
$params['sig'] = mailru_sign_server_server($params,$secret_key);

foreach($params as $k => $p)
$query[] = $k.'='.$p;


return 'http://www.appsmail.ru/plat...?' . join('&', $query);
}


function mailru_sign_server_server(array $request_params, $secret_key) {
ksort($request_params);
$params = '';
foreach ($request_params as $key => $value) {
$params .= "$key=$value";
}
return md5($params . $secret_key);
}