cannot connect from behind a proxy server

My brother works for a small company. He has access to their proxy server. His problem is that he cannot connect with Windows Messenger from his machine. If he tries another machine in the office, it works fine. His machine has full connectivity to the
Internet: he can surf the Web, write e-mails, get files off of the server, etc. He just can IM. Also, he cannot connect with other IM products (such as AOL, Trillian, or ICQ). What does he need to do to get his IM to work again?