As fadmin said:
In MAGT log file search for this entry:
Global Catalog Server (GCS) from the BlackBerry MAPI profile:
BES uses GC's; while GC's are also DC's ... not all DC's are GC's. Make sure you have at least 2 servers set as GC's if you plan on rebooting a GC.