Hi Defunct, welcome to the forums.
Rather than turn the firewall off, try putting the Firewall & Defense+ into "Training Mode" (right click systray icon).. don't do anything else in this mode, just run Left 4 Dead through its paces.. joining games, playing, hosting games, etc.. Then return the Firewall & Defense+ back to the normal modes (no, not disabled) & try it again.
Router: I don't have a router, but I've recently seen some free software that does router port forwarding for game, etc.. I'll dig it up.
edit: Opps.. CFP 2! Scrap the Defense+ bits & confirm your version please. Thanks.