Some Rust is okay
Section 12 of ASTM A 615-96a, "Standard Specification for Deformed and Plain Billet Steel Bars for Concrete Reinforcement," says that rust shall not be cause for rejection provided the weight, dimensions, cross-sectional area, and tensile properties of a hand-wire-brushed test specimen aren't less than the ASTM specification requires.
Section 7.4.2 of ACI 318-95, "Building Code Requirements for Structural Concrete," has a similar statement indicating that reinforcement with rust shall be considered satisfactory, provided the minimum dimensions (including height of deformations) and weight of a hand-wire-brushed test specimen aren't less than applicable ASTM specification requirements.