I' had this issue again last week...(such a waste of time- and it always seems to happen when a deadline is looming.....lol)
Anyway, I frantically tried many different solutions/work-around suggested here. Thanks everyone for sharing your tricks.
I stubbornly did not want to use the "donut-solution"....I wanted to "fix" it!
In this case, I did find a solution...The data frame of the map that I was having trouble with was rotated by -12.5 degrees. When I changed the rotation to 347.5 degrees (same rotation, different way of asking Arcmap to do it) my map exported perfectly. Maybe this work around will help another user out there.
Best of luck all of you fellows!
(and shame on ESRI for not posting anything in the entire, 2 year long thread!) This is a nasty nasty bug, that can really delay production!