I've been using same Netgear DG834N router. The fix for 80072745 error was to log into router setup page, go to Firewall rules. Option "Open IM ports" at the bottom of the page was selected, but it obviously did not work as Windows Live Messenger was blocked. Oddly, but Yahoo messenger and Skype worked fine in the same time.
The fix was to select CLOSE IM PORTS and click Apply button. Then select OPEN IM PORTS and click Apply button again. And voila
)
The WLM started working again on all computers in network behid the notorious Netgear DG834N router
Btw, DG834N router is great, but I would NEVER suggest it to anyone because it has such stupid setup procedure and have a number of stupid bugs which will drive non-proffessional user crasy!
