I had that happen as well. I noticed that it was because the parts list had been carried over through several versions of civil 3D. I believe it started from 2007 Civil 3D. So I did the same as you and started from the begining and recreated all my parts and rules. It took a while but it fixed all the errors. Before I did it, I tried going through all the routines that are set up to convert the old stuff into the new format, but it was still giving me problems.
Thanks for all of the replies. I was able to workaround by swapping parts (finally was able to do that). I simply used NO FRAME structures and all of my structures defaulted back to my finished grade for the rim elevations.