I advise you to use Trillian (or GAIM) at all costs. :p
If MSN Messenger and your router support uPNP, it might automatically open the correct ports for you.
I have both Trillian and Gaim and neither one worked.
MSN didn't start working for me again until this afternoon. A few other people told me they were having the same problem. Anyway, it seems to be done now.