Outlook 2003/Exchange 2003 Free/Busy Search not working

Our exchange server crashed not too long ago and we were able to rebuild exchange on a different server.  But now the Free/Busy search is not working.  We are running Exchange 2003 on a 2003 server and using Outlook 2003.  I checked in ESM and the SCHEDULE+ FREE BUSY folder is present.  The people on this exchange server use this feature extensively so I want to try and solve this for them asap.  I also tried giving people reviewer permissions to a specific person's calendar but that did not help.