My Pseudo code had an error, but I have got the following syntax to work ;

Dim MyParentObject As Webservice.ParentObjectClass = New Webservice.ParentObjectClass
Dim MyBuiltMessage(1) As WebService.MessageClass = New WebService.MessageClass

MyBuiltMessage(0).Property1 = "Hello"
MyBuiltMessage(0).Property2 = 1

MyParentObject.message = MyBuiltMessage

Thanks for pointing me in the right direction.

Gary.