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.