Why has my Android become half-rooted? I had rooted my Samsung Galaxy S 4G, and for some reason it seems to be only partially rooted now. What I mean by this is that while SuperUser is installed, apps such as BusyBox and Titanium Backup are complaining that they cannot get root access. Using apps from the Google Play store, I can neither remove the root or re-root the device. I cannot get to the Recovery menu because the key combinations done at startup just end up rebooting my device. Why is this happening and what can I do to fix it? Resetting the phone to factory settings does nothing.

Despite all this, AVG Antivirus is complaining that my device is rooted. So, what's up with that?
You probably have su installed (the program that allows you to become root) but it may lack the right permissions to run. In this scenario, AVG is probably just checking if su is installed but apps that need root fail to run. You might be able to change the file permission using adb and chmod (I don't know the exact command but may be easy to google for it).