I did want to mention to everyone.....
I can't see the navdata being the issue. Take the old FMC build and add the new Navdata. Maurice said it best earlier in the Post. The problem seems to lie in the addition or removals of the STAR. Not the NavData itself, but the way the FMC Adds the Data to the route.
So if you want download the older build FMC and add New Navdata.
Trev