Со временем все ок. Странно, что никто не заметил другого. В подпись запроса нужно вводить те же данные, что и в сам запрос (ну кроме самой подписи естественно). Т.е. если я указал format=JSON в запросе, то и в подпись надо это внести.
Два дня потратил, а собака-то была не глубоко зарыта.
Вот этот код нормально работает

Код:
$stringForSig = "api_id=" . API_ID
. "format=JSON"
. "method=secure.getBalance"
. "random=" . $random
. "timestamp=" . $timestamp
. "uid=" . $viewerId
. "v=2.0"
. API_SECRET;
$sig = md5($stringForSig);
$request = $apiUrl
. "?api_id=" . API_ID
. "&format=JSON"
. "&method=secure.getBalance"
. "&random=" . $random
. "×tamp=" . $timestamp
. "&uid=5495786"
. "&v=2.0"
. "&sig=".$sig;