Actually, it probably only deleted the binaries and didn't "uninstall" the programs from the RPM tables. I would go through the redhat-config-packages program, uninstall everything and then reinstall it. It probably won't get EVERYTHING that was deleted considering some of those packages will not uninstall b/c they are required by the system.
Hopefully, all of the redhat-config-* packages were not deleted. If so, check the /sbin and /bin directories.
Good luck