I've had the same problems using my backup and restore on some of the newer Cics I've installed. There is a post by foxtel about this same problem, a couple post back. He does mention a solution about getting the proper map file e-mailed to him, but does not go into detail about what he did with the mapfile. Maybe that post can point you in the right direction.
Hope that helps.

Kevin