Damian, I had a very similar thing happen. I had a simple screw that had tons of configurations. After using a macro to flip through the configurations, I saved it and it was around 50-60MB.
If I opened an assembly that had that screw in it in this bloated state, it would take forever but would open just fine. I then did a "Save As" to get the file size down to a reasonable size. Now, when I open an assembly that has that screw in any configuration other than the "last saved", I always get the 'ol "Parts Have Changed. Do you Want To Rebuild Blahh...Blahh....Blahh". Since I am NOT going to leave any of my library parts in this ridicules bloated state, I always get this error on basically every assembly I have.
SW2003 did not give you this error in this situation. I reported this in the beginning of SW2004 but nothing has ever become of it. I wish SW would fix this sh_t.