A small amount of rust is not a problem.  In fact, it will actually help the bond between the steel and concrete.  However, if there is excessive rust (flakes off when scraped), then it should be removed (wire brush, etc.).

Thank you very much Taro.  By the way, do you have any documents that can help me back up this information??  I am having problems with the inspection and they are requesting me some kind of proof...

Nigel M.

NigelM
When I was in school in Texas, I drove my car to the beach and it got damp from coastal fog.  After I returned home to Austin, the car continued to rust.  I always thought this was caused by salt.  
It would be wise to document the condition of the rebar and the composition of the concrete. If the structure falls down in 15 years it would be helpful to know what additives had been used in the concrete.  
Photos could be helpful.
roger,(a geologist)

The definitive reference on the subject of rust on rebar is:
Kemp, Brezny, and Unterspan "Effects of Rust and Scale on tth Bond Charactereistics of Deformed Reinforcing Bars" ACI Journal, Proceedings V.65, No. 9, Sept. 1968, pp. 743-756

The "Commentary on Builiding Code Requirements for Reinforced Concrete" (ACI 318-77) says:
"Research has shown that a normal amount of rust increases  bond.  Normal rough handling generally removes rust which is loose enough to injure the bond between the concrete and reinforcement."

Another reference worth reading is the following article in Concrete Construction magazine.  It discusses other common contanminants besides mill scale.

"How clean must rebar be?" by Bruce Suprenant and Ward Malisch - Concrete Construction June 1998.

Most of the codes say "..free of loose rust..". Notice 'loose' here, if your code is written like this.

One more reference...
From the Concrete Reinforcing Steel Institute (CRSI) Manual of Practice, paragraph 8.2, "Surface Condition of Reinforcement", rust and mill scale OK as long as overall dimensions/properties not affected.

I should mention that for the article I referenced, "other contaminants" includes dried concrete.  As many of you are aware, asking a contractor to clean anything and being sucessful is like drawing blood from a turnip - however when asking a contractor or laborer to remove dried concrete so that they can place wet concrete really stirs them up!