L'une des promesses électorales de Sarkozy était de réaliser une union de tous les pays méditerranéens. Cela n'en prend visiblement pas le chemin, si l'on en croit le quotidien algérien "Tout sur l'Algérie" :
"Depuis quelques jours, l’ambassadeur de France à Alger affiche un optimisme démesuré concernant l’état des relations algéro-françaises. Pour ce diplomate gaulliste – il est proche de la famille Debré-, fervent partisan d’une relation privilégiée entre Alger et Paris, la moindre initiative, comme la visite qu’effectue aujourd’hui une délégation du Medef à Alger, est une occasion pour se réjouir de « l'excellence » des relations entre les deux pays. Dans les faits, la situation est loin d’être aussi bonne que le laisse entendre l’ambassadeur de France. Depuis quelques semaines, Alger refuse systématiquement les demandes de visites émanant de hauts responsables français. Claude Guéant, Secrétaire général de l’Elysée et bras de droit de Nicolas Sarkozy, Brice Hortefeux, ministre de l’Intérieur et Eric Besson, ministre de l’Immigration, ont été priés de patienter. Certes, Nora Berra, Secrétaire d’Etat chargée des aînés, a effectué dimanche dernier une visite à Alger. Mais Alger pouvait difficilement refuser ce déplacement. Non seulement cette visite n’était pas politique, mais en Algérie, Mme Berra était venue parler d’un sujet sérieux et grave : la situation dramatique des retraités algériens vivant dans les foyers de la Sonacotra en France. Alger et Paris se concertent depuis quelques mois pour trouver une solution à ce drame. A Alger, les consignes sont claires : aucune visite politique avant le règlement définitif de l’affaire du diplomate Hasseni. Les Algériens estiment en effet que la relance des affaires des moines et les poursuites à l’encontre du diplomate algérien dans l’affaire Mecili sont destinées à faire pression sur Alger. Ce dernier veut en finir une fois pour toutes avec ces « provocations ». Les Français ont tenté d’expliquer que la justice de leur pays est indépendante. En vain. « Nous acceptons le fait que la justice française soit indépendante. Mais pourquoi Nicolas Sarkozy s’est-il mêlé de l’affaire des moines en faisant une déclaration dès le lendemain de son éclatement ? », s’interroge un responsable algérien. « Nous n’avons presque plus d’interlocuteurs à Alger. Il devient difficile même de faire passer des messages », reconnaît une source diplomatique française. Lors de sa visite de quelques heures à Alger, le 18 octobre, l’émir du Qatar, qui entretient de très bonnes relations à la fois avec Abdelaziz Bouteflika et Nicolas Sarkozy, a tenté une médiation. Mais ses chances de succès semblent minces : le différend entre Alger et Paris semble avoir atteint un niveau proche de la crise."
L'affaire des moines de Tibehirine selon Wikipedia :
En 2009, selon un général à la retraite, ancien attaché militaire à l'ambassade d'Alger, qui aurait recu les confidences d'un officier algérien dès 1996, les moines auraient été tués par erreur lors d'une opération menée par l'armée algérienne. Celle-ci a mitraillé un camp d'un hélicoptère, pensant qu'il abritait des membres du GIA. En effectuant une patrouille au sol, elle aurait découvert les corps sans vie des moines. Pour faire croire à un assassinat commis par les terroristes, elle aurait décapité les cadavres des moines. Le gouvernement francais de Alain Juppé aurait été au courant de cette affaire dès 1996 et aurait masqué la vérité à l'opinion publique. Le président Sarkozy a levé le secret défense sur cette affaire.