as Richard suggests,
Why not try it directly connected and remove the router from the equation.

Are you both using routers? Are you both using windows XP?
Does video work fine?

I am assuming you are using the final build of Messenger:

MSN Messenger FINAL 6.0.0602: (download below)
http://messenger.msn.com/

Have you tried reinstalling it? If you are using any firewalls, including XP's built in, hardware based, or software based firewalls, like sygate or zone alarm, try exiting them entirely and taking them out of the equation.

IF worse comes to worse, you can always use netmeeting or Windows Messenger (*only for XP Users) and see if it works.