I'm sure what you mean by "storing objects in a web service".
Here's one of my web methods:
<WebMethod(Description:="Authenticates a ReminderService user.", MessageName:="LoadUserByLogin")> _
Public Function getUser(ByVal sUsername As String, ByVal sPassword As String) As userReturnArgs
Return getUser(Nothing, sUsername, sPassword)
As you can see, the web service returns a custom data type. userReturnArgs is actually a class that contains another class. I have had no problems with doing this. I also have web methods that accept custom data types (my classes) as arguments and I have not had problems with this either.
Post some of the relevant code and maybe we can see what is wrong.
Work smarter, not harder