make sure content encryption is not turned on for contacts. also if these are company phones , they can have a policy that locks contacts preventing adds or edits.
RIM support info.
KB15244-What is Content Protection and Encryption on BlackBerry smartphone