A few explanations about some of the French terms you might see...
Anything labelled "colonial" refers to marine troops. Those were originally infantry units belonging to the navy (marine in French). They were created by Richelieu, as "troupes de marine" to form boarding parties aboard ships of the line, and expanded over time to serve as garrisons in colonies. They can be recognized by the anchors on their insignia.
In 1900, as there was less need for boarding parties on ships of the line, they changed their name from "troupes de marines" to "troupes coloniales" (or armée coloniale), and were attached to the ministry of colonies. In 1958, as there were less colonies to defend, they were renamed back as "troupes de marine", but still belong to the army (and they still refer to themselves as "la colo").
As a rule, units that have "colonial" in their name (infanterie coloniale, artillerie coloniale) are metropolitan (ie white conscript) outfits. Local units would be named "tirailleurs" and the country of origin : tirailleurs sénégalais, tirailleurs tonkinois, tirailleurs malgaches... There were, to my understanding, no cavalry regiments in the troupes coloniales, so your "colonial cavalry regiment" sounds a bit weird. I suspect those might be Chasseurs d'Afrique, or some light infantry unit (Bat' d'Af or so), reorganised as a recon element.
However, the "troupes colonials" are only part of the pciture. Units defending North Africa were not "troupes coloniales" but formed the Armée d'Afrique. As the colonials, they had european and local units, and had cavalry. European units included the Zouaves and Bataillons d'Afrique (infantry and light infantry), Chasseurs d'Afrique (cavalry), and the Foreign Legion (infantry, but foreign nationals). Whenever you see "Etranger" in the name of a unit, it means opened to foreign nationals, ie FFL (note that the Legion Etrangere belongs to Armée d'Afrique). Local infantry were tirailleurs and goumiers, cavalry was known as spahis.
So, in your post above, the BMEO, with the word Marine all around, is most certainly a unit from the armée coloniale (note the terms fusillier marin and transmission de marine). The REI and DBLE are FFL units, which belong to the Armée d'Afrique. Lieutenant de vaisseau is just the navy term for captain, OF-2 in NATO-speak. Capitaine de vaisseau (the head of BMEO) is OF-5, and the BMEO is a regiment-sized unit.
DBLE is demi brigade de légion étrangère. The term demi-brigade was used to replace the name "regiment" in the revolutionary era. It was then used to denote a smaller unit than a regiment. A regiment would have four, and then three battalions, a demi brigade would have two. For what I know, the 13th DBLE is the only unit that still retains this name.
Hope this helps. Just ask if you need specifics. I can probably help with contacts in Vincennes (did that for John recently, and his errand was probably much more complicated than anything you might need...).
< Message edited by fcharton -- 5/8/2013 10:41:24 PM >