The way you've described SHOULD work. In my experience, you do have to be very careful about having multiple bundles of the same project on a computer and multiple versions of audio/video files that have the same names, which may confuse Qlab's targeting. If your SM is receiving new workspaces/bundles from you and still has the old ones floating around that could cause issues.
My advice would be to create an entirely new bundle with the 'save bundle' option through the workspace, and make sure to give it a new name. Ask your SM to delete all files & previous versions. Then ask him to open the new project from the new bundle. QLab should be able to find all targets.
Another thought would be whether the bundle you're sending him does in fact have the targets intact, but does not have the audio device patched in the workspace preferences. This will cause all the cues to have the red X next to them. I've had QLab novices interpret this as having lost the link to the targeted files, when in fact it's just a device patching issue.
Best,
MV