Alright, first thing is that these free AV programs are frequently the malware itself, and it is VERY important for a User to be VERY clear on exactly what they are getting when they run an install, as removing them can be very difficult and time-consuming.
Generally, problems with a 3rd party application (like Avira) can be best & most-efficiently solved by uninstalling and reinstalling the software. It's free, and if it's a decent software it should uninstall quickly & completely (i.e. "cleanly") and reinstall with a minimum of hassle. Failure to perform at this level is a CLEAR indication that it is not a good software, and there are many others available that are equally good, such as AVG.
As to the service pack question, these are integrated into the Operating System, and not (to my knowledge) "installed" as a simple program would be. I don't think they can be "uninstalled" either. I also doubt they are the cause of your problem, nor do I think messing with them will help you.
I'm suspecting that you have some kind of infection (hence the attempts at System Restore) and that the infection has disabled your AV protection.
Try running TrendMicro's HouseCall
in order to get a general idea of what the status of your computer is.