Hi Chas
Not sure about the router side of things, but a couple of other things to check if you haven't already (and sorry if I'm stating the obvious...)
Which version of Messenger are you running? I never had any success with voice conversations until the about six months ago when the system finally seemed to get it right. I think the latest version is 7.5 (and I'm assuming this is MSN Messenger not Windows Messenger).
Also, have you gone through the Audio Setup wizard? This will at least tell you if Messenger is picking up your mic; if you have more than one audio program/mic this can alter the settings so you're using one mic and the computer is trying to use a different one!
If you can chat and send files via Messenger I wouldn't have thought it was a router problem otherwise it would be blocking the program altogether.
Have you tried skype, and does this work?
Again, sorry if I'm asking the obvious but it's always worth a try!