"He never doubts me."
Translation:Él nunca duda de mí.
There is an explanation here which talks about the use of dudar and dudar de. http://spanish.about.com/od/verbs-a-e/a/dudar.htm It also says "When followed by a noun or pronoun, dudar is usually used with the preposition de." so it sounds like this is just one of the things we have to remember.