Посмотрите на определение метода:
$mantis.mc_issue_relationship_add
# OUTPUT:
#
# OverloadDefinitions
# -------------------
# string mc_issue_relationship_add(string username, string password, string issue_id, Microsoft.PowerShell.Commands.NewWebserviceProxy.AutogeneratedTypes.WebServiceProxy1pi_soap_mantisconnect_php_wsdl.RelationshipData relationship)
Вы видите, что правильный тип - RelationshipData
$Relationship = New-Object ($mantis.GetType().Namespace + ".RelationshipData")