I just had the same issue and couldn't find a solution, it took a while to figure out so I thought I'd share the details here:
My local plugin has two files:
backup_local_PLUGINNAME_plugin.class.php
This has one function, define_module_plugin_structure which build the tree of nested elements and calls annotate_files.
restore_local_PLUGINNAME_plugin.class.php
This has one function process_ELEMENTTYPE for each element defined in the backup. Initially I tried to do add_related_files here but got the same error as Anthony - the issue is that this is happening in the context of the module not the activity and so it doesn't have the old context id to retrieve the mapping. I stepped through the backup code and found that the after_restore_module hook is called when the object has the right task object with the old context id defined. When I made the call here it all worked fine.