David,
Try adding a static route in your hosts file (%system%\drivers\etc\hosts) mapping the old management address to the new one and attempt to remove the device, see if it'll work this time. What we think had happened, is when you updated the management IP address, the IP address change did propagate back into our device connection cache, but didn't make it into the SCOM database (at an upper layer). Currently this is not a fully supported scenario. We always recommend removing the device first before changing the IP address on the management interface and re-discovering.
Let us know if the suggested workaround was effective. You can remove the static route in your hosts file, if you were able to successfully remove the 'old' device reference and rediscover the new one.
Julian