I have this sentence:
This man was an accomplice with the thief.
It sounds very unnatural to me as, correct me if I am wrong, "accomplice" conveys that the man was with the criminal i.e helping the criminal, so use of "with" in the sentence makes it superfluous.
http://www.yourdictionary.com/accomplice states that both "with" and "of" can be used. Please specify where to use which one.