Not an iPhone developer, so let me know if this does not make any sense.
Is the Facebook public key hardcoded on the app? Since presumably the app needs Facebook to run, they need to be connected to the internet, so maybe there could've been some phone home page where the app gets the key (caches it for some amount of time) and uses that -- it won't fix the issue of Facebook revoking keys, but at least if it gets fixed (with Facebook) you don't have to resubmit an app and wait for Apple.