I ran into that error today but found a way around it. Here's the scoop.
I fired up a VPC with Dynamics CRM 4.0 Rollup 13 today and added 21 attributes to the Contact entity, which was previously unmodified. I then exported the Contact entity to XML and send the resulting zip file to someone I work with. He has the main VPC and needed some help. Anyway, he attempted to import the Contact entity into another CRM Rollup 13 instance and got the error I mentioned above.
After calling each other crazy and demanding proof that we were both running Rollup 13 (we were... not crazy, but running rollup 13, well maybe both), I exported the Contact entity and immediately re-imported the zip file. Bam! Same error... on the same CRM instance! Grrrrr.
The "solution"? I removed the node "<EntityRelationship Name="contact_activity_parties">
I'm sure, I have to believe, okay I hope (but not holding my breath) that Microsoft has made customization import/export rock solid between rollups in Dynamics CRM 2011. I can understand that moving customizations between different rollups is hard for Microsoft to get right but exporting and re-importing on the same server, within only 38 seconds lapsing between the time the zip file plopped onto C: to when I optimistically clicked the Import button -- for that not to work is, well, causing me to write this blog post instead of working. So with that, onward to the next challenge.