Thank you Jroffman for the additional details and for reporting back. 
Indeed, it appears the LSP is damaged in some form and/or missing.
No doubt, a possible after effect of the result of the threat that was found.
First, try running the LSPfix utility this time by right clicking and choosing
“Run as Administrator” and see if that makes a difference. Possible
that it could not access the key due to the utility not being run as
“admin” as described above, even though you are logged on as Admin.
Also, see this from Microsoft: Some of the links may or may not be helpful, but I am trying to initially gather
what details directly address your situation: First link should help you reset your winsock2:
http://answers.microsoft.com/en-us/windows/forum/windows_7-system/resettingrepairingreinstalling-winsock2-testing/aa044f6b-00e2-406b-8edb-cba5c4799cf2 Review it carefully, good information, but if not helpful see the following: Some details pertain to Vista, which often work for Windows 7:
http://support.microsoft.com/kb/811259#LetMeFixItMyselfAlways
The second link gives details about fixing corrupted LSP for XP and Vista, the Vista details
may be helpful and work on Windows 7.
"Manual steps to determine whether the Winsock2 key is corrupted for Windows Vista users
Click Start, click Run, type Msinfo32, and then click OK.
Expand Components, expand Network, and then click Protocol.
Ten sections appear under Protocol. [u]The section headings will include the following names if the Winsock2 key is undamaged:[/u]
MSAFD Tcpip [TCP/IP]
MSAFD Tcpip [UDP/IP]
MSAFD Tcpip [TCP/IPv6]
MSAFD Tcpip [UDP/IPv6]
RSVP UDP Service Provider
RSVP TCP Service Provider
RSVP UDPv6 Service Provider
RSVP TCPv6 Service Provider
MSAFD NetBIOS [\Device\NetBT_Tcpip...
MSAFD NetBIOS [\Device\NetBT_Tcpip...
MSAFD NetBIOS [\Device\NetBT_Tcpip...
MSAFD NetBIOS [\Device\NetBT_Tcpip...
MSAFD NetBIOS [\Device\NetBT_Tcpip...
MSAFD NetBIOS [\Device\NetBT_Tcpip...
If the names are anything different from those in this list, the Winsock2 key is corrupted, or you have a third-party add-on such as proxy software installed.
If you have a third-party add-on installed, the name of the add-on will replace the letters “MSAFD” in the list.
If there are more than ten sections in the list, you have third-party additions installed.
If there are fewer than ten sections, there is information missing."
Also this:
"Manual steps to recover from Winsock2 corruption for Windows Vista users
Winsock corruption can cause connectivity problems. To resolve this issue by using Network Diagnostics in Windows Vista, follow these steps:
Click Start
and then click Network.
Click Network and Sharing Center.
In the Network and Sharing Center box, click Diagnose and Repair.
Note You may also access the Network and Sharing Center in Control Panel.
Reset Winsock for Windows Vista
To reset Winsock for Windows Vista, follow these steps:
Click Start, type cmd in the Start Search box, right-click cmd.exe, click Run as administrator, and then press Continue.
Type netsh winsock reset at the command prompt, and then press ENTER.
Note If the command is typed incorrectly, you will receive an error message. Type the command again. When the command is completed successfully, a confirmation appears, followed by a new command prompt. Then, go to step 3.
Type exit, and then press ENTER."
The above we’ll just figure is at least a start on tracking this down with the winsock issues. I hope it helps in some way
or at the very least offers some insight as to how to proceed further.
2) In regards to the Windows Firewall error, I was not surprised to read your issue with this considering the LSP
is damaged or missing. Perhaps the following will be of some insight as well:
http://social.technet.microsoft.com/Forums/en/w7itprosecurity/thread/b9bbd758-e3d6-44c1-a75d-bc94a74704d1
There are some links within this that may be helpful. Also take a look at this please:
http://support.microsoft.com/kb/968002
“Error 0x80070424 occurs when you use Windows Update, Microsoft Update, or Windows Firewall”
It may or may not apply, but worth reviewing. Sometimes, these issues with winsock2 are not easily resolved, but
at least from your information, it has been confirmed that the LSP is affected, which is what i had suspected, this in turn
likely affects of course your firewall.
Here is one that may be more helpful as it deals with Windows 7 firewall error code you are having:
http://answers.microsoft.com/en-us/windows/forum/windows_7-security/i-get-error-0x80070424-when-trying-to-turn-on/908a3f7e-1fc2-4083-a420-91e03310e450?auth=1
One more link:
http://www.sevenforums.com/system-security/200214-window-7-firewall-error-code-0x80070424.html
Also, it is possible you may need to perform a ‘repair installation’ but it may be avoidable if any of the above is helpful.
I will continue to do my best to gather additional information, please report back after carefully reviewing the above details. Please
review carefully, especially the first 2 links, take one step at a time as we attempt to remedy this.
Please let us know if you find any resolution.
All my best!
Jim