В общем решил проблему. Честно не совсем понял в чем разница, но нагуглил как другие решали подобные проблемы.
Вместо переданных данных в такой форме в requests.post:
r = requests.post(server['upload_url'], files={'photo': open(path_img, "rb")})
Делаем так:
data = {}
files = {'photo': (instance.img_name(), open(path_img, 'rb'))}
url = server['upload_url'].split('?')[0]
for key, value in urlparse.parse_qs(server['upload_url'].split('?')[1]).iteritems():
data[key] = value
r = requests.post(url, data, files=files)
instance.img_name() - имя файла с фото
url - полученный адрес от ВК (только адрес, без параметров)
data - словарь параметров в url