Apple - What should I do when the menu bar seems frozen/unresponsive?

SystemUIServer is the process responsible for the menu bar and any menu extras. You can restart it in Terminal using:

killall SystemUIServer

In addition to the Terminal option @Nathan Greenstein gave, you can also force quit the SystemUIServer process using the Activity Monitor utility.

BTW, SystemUIServer is only responsible for the menu items (i.e. the right side of the menu bar). If more than that is frozen, this may not do the trick. OTOH, if it is just SystemUIServer, you probably have a buggy menu item and should try to isolate which one is causing the problem and remove or update it.