I have come across this problem frequently recently and wonder what i am doing wrong.
I was installing Sygate Personal Firewall on WinXP and the install all went acording to plan. Up until when i had to restart the PC, once restarted Sygate didnt load automagically and when i clicked it in the start menu it just died out. Either way it caused things like runddl (whatever that is) to crash as well.
When i removed SPF al was fine again.
So i proceded to go and get Zonealarm, low and behold the results were almost identical.
Before this i have tried to install SPF on a few machines which rejected it in much the same way, but they accepted Zonealarm.
Sygate has been acquired by Symantec, who promptly discontinued the free version of the firewall. Existing copies won't update any more. This might explain the problem with SPF, dunno about ZA, I've never had any problems with that.