What version of 6.3 is this? If it's 6.3(1) then there is a known bug with MSN Messenger not working through the PIX (CSCeb45344, not visible from outside as it was found in pre-production testing). The fix is available in 6.3(2), but this code is not available due to another sever bug. You can open a TAC case and get the latest interim release of 6.3(2) made available to you for testing if you like.
If you're running 6.3(2) code already, then we need some more information to resolve this. Can you turn on logging on the PIX, try a connection and then send us the syslog output (see http://www.cisco.com/univercd/cc/td/doc/product/iaabu/pix/pix_sw/v_63/cmdref/gl.htm#1028090 for details).
