It shouldn't have anything to do with your changing the DME. It's not unheard of for the circuitry in the key to get damaged, so trying another key will narrow things down. Yes, the new master key will be pre-programmed. On early EWS II cars (which your case should be), there are 10 keys made and 3 are given out during the initial purchase of the vehicle, the other seven are stored away in Munich. On later models, a blank can be programmed by the dealer, but still only up to 10 can be produced. At least that's what I've read anyhow.
You mentioned on another forum that the starter was just replaced. It could be that its wiring was not secured properly. You might want to have your installer reinspect his work, just to eliminate that possibility. It's also not uncommon for new/remanufactured starters to fail immediately and inexplicably. Good luck and let us know how things work out.