Usually that only happens if the path to one or the other has changed or both. If you move or rename the Illustrator file, that might break the link to placed files. And obviously, if you move or rename the placed file, that will definitely break the link.
If you move both files, the link will also be broken. I commonly transport Illustrator files on a thumb drive, and even if I keep the relative locations the same as on my desktop at home (a references folder inside my Illustrator docs folder), I still have to relink the files when I open the .ai at school.
Actually, removable media in general might cause a problem if the computer is not assigning the same drive letter to the device every time.