I was missing a cast, now the code works.
I will write it here, hoping it will of help to someone else in the future:
/// <summary>
/// Restores a record from the Audit history
/// </summary>
/// <param name="organization">Organization service to be invoked</param>
/// <param name="auditId">Id of the audit record to be used during the restore operation</param>
/// <returns>A bool showing if the method succeded</returns>
public static bool RecoverEntity(IOrganizationService organization, Guid auditId)
{
// create retrieve audit detail request object
var request =new RetrieveAuditDetailsRequest {AuditId = auditId};
//execute request and retrieve response
var response = (RetrieveAuditDetailsResponse)organization.Execute(request);
//create auditDetail variable and assign its value
AuditDetail auditDetail = response.AuditDetail;
//type cast audtitDetail as AttributeAuditDetail
var attributeAuditDetail = auditDetail as AttributeAuditDetail;
//create the deleted record
if (attributeAuditDetail!=null)
organization.Create(attributeAuditDetail.OldValue);
else
{
return false;
}
return true;
}