try these steps

1. check the date/time is properly set on the problematic pcs
2. turn off the firewalls on the pc and try again. If XP sp2 is
used, you need to add msn messenger in its allowed application list.