I am also having this problem. My MXD is in my project's "root" folder, along with the 4 file geodatabases that it references.
The MXD is rather complex: 14 data frames, about 90 feature layers and table views, and numerous layout elements. There are no references to data outside of the root folder, and no shapefiles.
After copying the entire project (the root folder) to a new location (e.g. "My Documents" on the C: drive), the paths all reflect the correct new location..... HOWEVER.....
If I disconnect from my work network (by disabling wireless) and open the MXD using a "borrowed" Advanced Desktop license, then the source paths for several (not all) data frames are broken. I can't find a unique common trait among the data frames with broken layer sources.
Another observation: If I reconnect the wireless and reopen the same MXD (without having saved it with the broken paths), the sources are fine. If I stay working offline, the broken sources sources can all be fixed by manually reconnecting one layer to its datasource, BUT... if I save the "fixed" MXD, close it, and then open it again, the same sources are broken *again*.
Any idea what else might be befuddling the relative paths in this case?