I'm happy to report that this has now been solved on our end :).
We had a dodgy CA file that was leading to all sorts of problems, this 
being one of them.
Thank you for your patience :)

I've just installed HTTP_REQUEST2 to see if it would change anything 
but got the same error message.

The facebook urls are *always* https.  SSL on Horde shouldn't make a 
difference, unless maybe your certificate is not valid and facebook 
has issues with that? Just guessing, my setup works fine regardless of 
if I'm logged in under https or http

I wonder if it could be an SSL thing or were your test setups also using SSL?

I can't de-authorize the app, because the authorization was never 
given, so it doesn't appear in my list of apps.

There is an Access Token with origin:Unknown and Permissions:None

I'm out of ideas then.  Sounds like something is broken on your setup 
then.  Try making sure you deauthorize the app in facebook, and clear 
the user's facebook pref. Maybe something is corrupt somewhere.

I've tried the traditional view, but it didn't change anything.
I have a top menu and a left one, but nothing is using iframes as far 
as I can tell.

I've tried from another computer and another browser as well in case 
some extension was in the way, but I get exactly the same message.

Ah, wait. I bet you are trying this while the prefs are displayed in 
an Ajax view, right? Facebook requires the authentication screens to 
be top-level i.e., not in a frame/iframe.  This doesn't play well at 
the moment with the way prefs are displayed in the dynamic views.

You'll have to authorize the app via the traditional view for now.

Here is something I've noticed.
If I'm already logged in, then the calls don't come from Facebook.
If I'm not logged in then I'm not even asked to authorize the app, I 
get redirected straight to Horde.

And the code is the same for both calls, in both cases

Yes. Multiple times. The auth method *did* change a little while ago, 
and our library was refactored to work with the OAuth2 mechanism that 
Facebook now uses.

Yeah, but the first (2) calls should come from Facebook, not from the 
horde prefs page.. e.g.,

127.0.0.1 localhost - [14/Jul/2011:19:18:15 -0400] "GET 
/horde/services/facebook?code=xxxx HTTP/1.1" 301 0 "-" "Mozilla/5.0 
(Macintosh; Intel Mac OS X 10.6; rv:5.0.1) Gecko/20100101 Firefox/5.0.1"
127.0.0.1 localhost - [14/Jul/2011:19:18:16 -0400] "GET 
/horde/services/facebook/?code=yyyy HTTP/1.1" 302 0 "-" "Mozilla/5.0 
(Macintosh; Intel Mac OS X 10.6; rv:5.0.1) Gecko/20100101 Firefox/5.0.1"
127.0.0.1 localhost - [14/Jul/2011:19:18:18 -0400] "GET 
/horde/services/prefs.php?app=horde&group=facebook HTTP/1.1" 200 15879 
"-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:5.0.1) 
Gecko/20100101 Firefox/5.0.1"
No, that's expected. The authentication is a two step method. You will 
notice that the code returned in both calls is different. It's the 
final code that is considered the auth_token.

Have you tried authorizing a new app? Maybe something has changed on 
FB's end and we need to change a setting or two to make it work?

Well, the last call is probably the UI refresh. There usually is 
another call to sidebarUpdate, right after that.

What I find strange is the double call to services/facebook, but I 
guess it's Facebook trying to find a working URL?

I did check my settings and they look correct.

Ah, wait. I misread the log entry. I have no idea why the prefs page 
is listed as the referrer for that request. It should be coming 
directly from Facebook, not from Horde.  I can't reproduce this at all.

Are you *sure* you are using the services/facebook URL as the callback 
and NOT services/prefs? Facebook should not be requesting the prefs 
page, but the services/facebook page.

This is what I see in Apache's logs after I click on the Facebook button

  [10/Jul/2011:23:51:30 +0200] "GET 
/webmail/services/facebook?code=xxxx HTTP/1.1" 301 2677 
"https://sub.domain.com/webmail/services/prefs.php?app=horde&group=facebook"
  [10/Jul/2011:23:51:30 +0200] "GET 
/webmail/services/facebook/?code=xxxx  HTTP/1.1" 302 314 
"https://sub.domain.com/webmail/services/prefs.php?app=horde&group=facebook"
  [10/Jul/2011:23:51:31 +0200] "GET 
/webmail/services/prefs.php?app=horde&group=facebook HTTP/1.1" 200 
7450 
"https://sub.domain.com/webmail/services/prefs.php?app=horde&group=facebook"
  [10/Jul/2011:23:51:31 +0200] "GET /webmail/static/abcd1234.css 
HTTP/1.1" 304 117 
"https://sub.domain.com/webmail/services/prefs.php?app=horde&group=facebook"
  [10/Jul/2011:23:51:32 +0200] "POST 
/webmail/services/ajax.php/horde/sidebarUpdate HTTP/1.1" 200 2234 
"https://sub.domain.com/webmail/services/prefs.php?app=horde&group=facebook"

I've followed the instructions and used
https://sub.domain.com/webmail/services/facebook/

I've tried with domain:
sub.domain.com and domain.com (just now)

Unable to reproduce this. What callback url are you providing to facebook?

cURL support        enabled
cURL Information        7.21.6
Age        3
Features
AsynchDNS        No
Debug        No
GSS-Negotiate        No
IDN        Yes
IPv6        Yes
Largefile        Yes
NTLM        Yes
SPNEGO        No
SSL        Yes
SSPI        No
krb4        No
libz        Yes
CharConv        No
Protocols        dict, ftp, ftps, gopher, http, https, imap, imaps, pop3, 
pop3s, rtsp, smtp, smtps, telnet, tftp
Host        x86_64-unknown-freebsd8.2
SSL Version        OpenSSL/1.0.0d
ZLib Version        1.2.5


allow_url_fopen enabled

PECL Http extension is not installed

Do you know which Horde_Http_Client class you are using? If you can't 
figure out what class is being created, just check for the following 
support in PHP:

PECL Http extension
curl extension
or allow_url_fopen enabled

Thanks for the 'exception' fix.

I now get a more meaningful error message in Horde:
Temporarily unable to connect with Facebook, Please try again.

This happens right after coming back from FB, after authorisation.
There is no PHP error anymore, but still the same message in the Horde log:
2011-07-05T18:50:24+01:00 ERR: HORDE [horde] users.getLoggedInUser 
requires a session_key [pid 10960 on line 449 of 
"/webmail/lib/Prefs/Ui.php"]

This error message is irrelevant.  It is thrown when PHP fatally exits 
in either the initialization or shutdown stage (I can't remember which 
one) - I *think* it has to do with APC, but don't quote me on it.

Fixed.
No idea. The constant is definitely defined in the class, in the 
*same* file that it's used. Are you sure you are using up to date git 
code?
This is most likely the path to your pear libraries. Did you install 
or link the libraries via PEAR? If not, then your include_path is 
probably wrong and you are loading an older version of the package 
than you think you are.

Changes have been made in Git for this ticket:

Bug: 10311 Fix throwing exception

  1 files changed, 2 insertions(+), 1 deletions(-)
http://git.horde.org/horde-git/-/commit/34b4b801918536e96838fe061be8ddf6bf1f5f5e

Here is more useful info
[05-Jul-2011 17:39:52] PHP Fatal error:  Call to undefined function 
Horde_Service_Facebook_Exception() in 
/usr/local/lib/php/Horde/Service/Facebook/Auth.php on line 96
[05-Jul-2011 17:39:52] PHP Fatal error:  Undefined class constant 
'MAX_SIZE' in /usr/local/lib/php/Horde/Memcache.php on line 293

The path to Horde is wrong, it's not installed in /usr/local/lib/php/Horde

Users tying to authorize Facebook are getting an error 500 and this is 
what I can see in the logs:
2011-07-05T17:39:42+01:00 ERR: HORDE [horde] users.getLoggedInUser 
requires a session_key [pid 9574 on line 449 of 
"/webmail/lib/Prefs/Ui.php"]