When you package an InDesign document, the way I understand it, is that InDesign basically recreates the location path for all of the links to the computer version of "within a links folder that is located in the same folder as the InDesign file."
This way, when you send the InDesign file to someone, as long as they save the links folder in the same place as the InDesign file, the links do not need to be updated.
However, it could be that something about your particular workflow has "broken" this connection. In your place, I would probably be tempted to lose a day or two into trying to figure out why it happened--but let's be honest, you probably just want to solve the problem and move forward with your work.
I think the easiest way to solve this problem would be to make sure that all of the links in your InDesign file are correctly linked. If any of these links are located in a file called "Links," then you need to rename that folder, and go back into your InDesign file and update the link location (which should be fairly easy as InDesign by default looks for additional missing links in the folder once you relink one file).
Once your links are all correctly linked, then use the "Package" option to have InDesign create a new folder called "Links" and place a copy of all of the linked files into that new folder.
Once you have packaged the InDesign document, you can save it, and all of your links should then be directed to the new Links folder that was just created.
If you still have trouble, it is time to try resetting your preferences in InDesign.