This is a bug report rather than a support request; I've tracked down the problem with Cole's help.
When using Ultimate Facebook on a WPMU site, head to the settings panel of the network admin (not of a specific site). Even if the API and Secret keys are entered correctly, the system will appear to not be able to connect. If a subsite is configured properly, it will connect file and a green check mark will appear.
The culprit is around line 162 of plugin_settings.php. If you're in the network admin section, the script makes sure the APIs aren't empty, but doesn't try to connect to Facebook one way or the other. It's confusing to admins, because it looks like the system is trying and trying and can't connect to Facebook (because of the animated GIF loader that is displayed by default).