My best guess is this: when you download and install an app from the market or other sources, there's a bit of "handshaking" going on to let the system know what apps are there, or for the app itself to know what system resources are available. When you restore an app, it's already gone through the process, and carries over the info from whatever ROM was there previously, and freaks out when the handshake info doesn't match.
Put it another way, let's say I'm an app. If I'm told I'm moving from city A to city B, it's pretty easy to adjust to my new surroundings, regardless of the changes. On the other hand, if I'm living in an apartment and am told to go to sleep so I can be packed in a box, bet your bottom dollar I'm gonna start flinging poo if I wake up to find myself in a 10ft x 10ft cardboard shack.