Nick Fury holds the military rank of colonel in the original canon of the Marvel universe. In the new Marvel Movie Universe, is Fury still Colonel Fury? I only remember him being referred to as "Director Fury" in the Avengers film.
Short Answer: probably not.
The Ultimate Nick Fury, whom the cinematic version is largely based on, is a colonel and a war hero, having participated in the Cold and Gulf wars in some capacity.
It's important to remember that S.H.I.E.L.D is not a military division despite having access to equipment and assets otherwise only available to military. The Earth 616 version was originally a law-enforcement version (which might have ranks such as colonels), but has since been updated to being a government agency, which typically do not have those ranks. Similarly, Ultimate SHIELD was a military organization. The Earth 199999 version, however, was founded by Howard Stark and possibly Fury - implying that it has never been a military organization.
My guesstimate is that Colonel was his highest rank before joining S.H.I.E.L.D., and though it is unclear what he was referred to as before becoming its Director, both titles may now be applicable.
In all of the official MCU comics up until at least about the end of Hulk and Iron Man 2, he is almost exclusively referred to as Colonel Fury, even by Coulson: