According to gcmap.com a great circle route would go over Mauritania, Western Sahara, a tiny bit of Morocco, Portugal, the very north of Spain and Brittany. The oversea bit of the route would pass quite close to the Canaries (which could raise the Spanish airspace issue, I suppose) but it does seem odd that they would be that difficult about a RAF flight (a fellow NATO member, after all) which hadn't originated in, or was going to, Gibraltar.
A quick and dirty google maps estimate suggests that the longer route adds about 300 miles to the flight; not a lot, I guess. I'm still wondering why, though!