I've just had to deal with this very problem after installing Wise Care 365 and following all its suggestions for optimising my XP Pro system (recently reinstalled, and laboriously shoved though Windows Update).
I'm not sure exactly what I changed (almost certainly something in the WiseCare StartUpServices facility), but the net result was Microsoft Security Essentials wasn't working "because the app's service stopped", and clicking on the rather promising Start now button didn't apparently do anything.
After calling on my Google-fu, I ended up in Administrative Tools - > Services, where I restarted the Microsoft Antimalware service. Bingo! - Security Essentials icon immediately changed from red to green!
All was not sweetness and light though, since I had to restart the service every time the machine booted up. After further investigation I discovered that the Microsoft Antimalware service depends on Remote Procedure Call (RPC), which was set to StartUp type Manual. I don't really understand things at this level - but I'd just made a complete Paragon system backup anyway, so I changed it to Automatic. And for good measure I changed Antimalware - > Recovery -> Subsequent failures to Restart the service.
Everything works just dandy now, whether I understand it or not. A full reinstall is always daunting, but it got my house PC boot time down from 4 minutes to less than 1, so it'll be well worth the time spent.
@Nironan12 - What method worked, was it due to not giving it time or was the service not set to automatic? – William Hilsum – 2010-09-17T21:15:27.873
The service wasn't set to automatic, it was on manual. – None – 2010-09-18T02:36:33.923
@Nironan12 Cool, glad I could help. – William Hilsum – 2010-09-18T10:23:50.260