I have the same exact problem. Linksys router since about 6 years or so, but MSN has been doing that for about 6 months or a year.
Also, it won't remember the display names others give themselves when I re-log. For instance, say Bob and I are on, but if we both log off and then, only I re-log, MSN will show me "bob@hotmail.com" instead of "Bob". This is also annoying
Any solution?