Not sure. I've run into this before. This may be the 3rd incidence I've heard of Security Center being fooled. There is, obviously, something left over on your system. Files, and more likely, registry entries. Of course, you could live with it, although then, technically. you wouldn't have monitoring of your real Anti-Virus. But really, you'd still know your AV was working through it's own notification. Security Center is mostly valuable as an indication of whether the Windows firewall is turned on, if you're even using it, and what your Windows Update download setting is. Other than that, it's simply a central place where you can access some of the Windows security features to change settings. Really, it's value as a security monitor is limited. An, as you can see, is quality as a security monitor is certainly limited.
I had BitDefender's online scan on my machine, and it didn't uninstall properly. So Security Center still thought I was using BitDefender after I'd switched to Avira. I don't remember whether just cleaning out the rogue files fixed it, or whether I had to delete it's registry entries, too. Fixing the registry isn't the horror story that you've heard, you just have to back it up first, and BE SURE of what you're deleting or DON'T delete it. I have never screwed up a registry, but that's because I religiously follow the above rule.
Security Essentials probably left folders in AppData folder (it's inside your User folder for whatever account your always logged in as), Program Data (right below Program Files in your C drive folders) or Common Files in your Program Files folder. Or all 3. You can look for those 3 folders manually. You can also run searches, like "Security Essentials" or Essentials. I don't know if MS abbreviates the folders. More likely, though, you'll have to search the registry for the rogue entries.
Click the start button, and then type regedit into the Search box, or, if your using the Classic Menu: Start>Run>(type)Regedit. Click, meaning highlight, Computer in Regedit, if it isn't already. Then click File>Export. That will give you a Save dialog box and you can save a backup copy of the registry. Or you can highlight any registry entries that you may delete later and just save a copy of whatever you deleted. Then if you want to replace them, or the whole registry, one way is to just right click on the saved file and select the merge option at the top of the menu.
In the edit menu, you'll see the separate find and find next commands, and their standard shortcuts - Control F and F3. You can search for Micorsoft Security Essentials keys and delete them. And, as I've said, if you don't want to save the whole registry, you can select the keys and export them before you delete them, so you can remerge them back in, just in case. But, deleting keys - or even whole folders of keys - that your SURE came from Microsoft Security Essentials is highly unlikely to give you problems.
Or you can just live with the false notification. In reality, it isn't likely to cause you any real problems. It'll just be annoying. Annoying, gee, sounds like a Microsoft product, doesn't it.
In any case, good luck! :)