Go to start > run, type services.msc and press enter.
Near the bottom of the list should be a service called Windows Firewall/Internet Connection Sharing. Double-click on the service and set the startup type to automatic.
If the startup type was manual or disabled before, that's probably the source of your problem. If the startup type was already set to automatic, I'm not sure what the problem could be.
Are you running Vista? If so, that's probably why the Windows Firewall service didn't exist.
Do you have another software firewall? If so, that's probably what's disabling the Windows firewall. It's best not to run two software firewalls side by side, as that can cause conflicts.