It was not easy to find a fix (there are many results in google for variations of the same problem) but in the end I found out why I am experiencing this, so I'm leaving a note here for reference.
In Fedora 14 I installed Firefox 5 from Spot's personal repository, so I had to change the default command to run on URL clicks from "firefox %s" to "firefox5 %s". The problem is that I ported the /home directory to the new installation, so it inherited that settings that is obviously wrong now.
Unfortunately, I could not find anything in the GNOME 3 interface to fix it, so I had to resort to the command line:
This shows the issue:
$ gconftool-2 -g /desktop/gnome/url-handlers/http/command firefox5 %s
And this is the fix:
$ gconftool-2 -s /desktop/gnome/url-handlers/http/command -t string "firefox %s" $ gconftool-2 -s /desktop/gnome/url-handlers/https/command -t string "firefox %s"