http://msdn.microsoft.com/en-us/library/system.runtime.serialization.datacontractserializer_members.aspx

So as it turns out, your XML stream must have the XML Nodes in Alphabetical Order when trying to deserialize XML data into an object.  Very wierd.