Strange network problem Vista

Recently, my computer (running Vista Ultimate) does not discover my network (wired) sometimes when I start up my computer. I have to restart it a couple of times before it finally realizes it's connected to a network.

In my event log, the only error message that's listed when this happens is:
"Windows Firewall was unable to notify the user that it blocked an application from accepting incoming connections on the network." The "application" is lsass.exe according to event details.

Now, the only thing I remember doing before all this happened was installing Albany (which came with Live OneCare). Immediately after, I started experiencing this problem. Since then, I've removed OneCare and the problem persists.

Any ideas why I'm having this problem?

I'm right now convinced it's a firewall issue, like an app trying to use the network before the Firewall is loaded, and Vista locking down network resources, but I'm not sure.