Я думаю, что ваше тело не так, тело - это объект json, вероятно, что-то вроде этого
msg_labels = {'removeLabelIds': ['INBOX'], 'addLabelIds': []}
message = service.users().messages().modify(userId=user_id, id=msg_id,
body=msg_labels).execute()
Возможно, вы захотите проверить документированный пример, мой python очень простой messages.modify python