It sounds like for some reason it's not able to look up all posts from the import_map table, or possibly the import_map table didn't get populated correctly during the import.
Are the old links that are working formatted differently than those that are not?
